BZOJ 2521 [Shoi2010] 最小生成树

发布于 2017-08-17  162 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=2521

题意:每次操作可以选择一条边权值不变,别的权值都减一,问使得某边成为最小生成树的必须边至少要几次操作。


首先有个显然的转化,别的都减一相当于选择一条边权值加一,会方便考虑。

考虑最小生成树的构建过程,一条边是必须边当且仅当只有它能联通两端点所在联通块。那么我们删掉这条边,使得得到的新图,两端点不连通即可。

就是显然的最小割模型了... 考虑到一条边能对我们选定的边构成“竞争”关系当且仅当这条边权值小于等于选定边,设选定边为 L,那么就可以重新构图,对于满足\(w_i<w_L\) 的边,连一条权值为\(w_L-w_i+1\) 的边即可

居然 1A..

 

 


一个非常弱的准退役OIER