bzoj2521[Shoi2010]最小生成树

题目链接

bzoj2521

对不起这个题权限题……

抱歉……我是权限狗(雾

题解

很玄学的一道题,他要求选的某条边一定要在最小生成树中……可以做出对应的修改就是除了这条边以外的所有的边权都加一,转化一下可以理解为将这条边的权值减一

继续考虑考虑最小生成树的性质,首先是两个集合不相交,其次就是这条边的权值在前\(n-1\)个。(这里\(n\)指边数)

可以考虑一下集合不相交的性质可以转换成网络流当中割的性质,因为要求最小代价,所以也就类比于要求一个最小割,源汇点分别为题中给定的边的起点和终点。

边的容量?因为在kruskal中,如果所有的边在经过排序之后,给定的边之前有边能使得源汇联通,则说明这条给定的边一定不会被选中,要使得这条边一定被选中,那将一条边从中移除就得要求这条边\(i\)的权值严格大于等于给定的边,也就是说,代价为\(qc[lab]-qc[i]+1\)。

所以只用把权值小于等于给定边的权值的边加入网络中,容量设为移除的代价\(qc[lab]-qc[i]+1\),然后跑一发最小割。

最后的答案即为代价。

为什么这么水的一道题我总感觉会讲不清楚啊……神烦

最近心态很炸,难受啊金轮~~~


By:Wahacer

2018.4.11

16:59

发表评论

电子邮件地址不会被公开。 必填项已用*标注