HDU 5624 Reconstruction

正文索引 [隐藏]

传送门:http://acm.hdu.edu.cn/showproblem.php?pid=5624

题目翻译

http://bestcoder.hdu.edu.cn/contests/contest_chineseproblem.php?cid=670&pid=1004

题解

首先很Naive的做法就是,枚举最小边,然后做最小生成树,这样会TLE。
我们想到可以动态做一个最小生成树,我们把所有边从大到小排序。
每次插入一条边
如果插入使树出现环,按照最小生成树的性质,我们应该删掉这个环上的费用最大的边,然后插入这条边。
如果插入不导致环的出现,那么直接插入即可。
然后用一个multiset,维护每次更新之后最大值和最小值的差即可。

代码