一脸懵逼
by 2016it05liyujie @ 2016-10-11 17:41:30
以下为出题人给的题解：
要使生成树为最小生成树，那么当树上一条边去掉后，树呗分成两部分，其它的能使树连通的边的权不能大于去掉边的权。
我们定义去掉树上某边，再加入其它边树仍连通，那么树边与加入边相关，将所有边看成点，相关边相连，于是树边和加入边构成一个二分图。
后于是问题转化为：二分图左边的每个点权值可以减小，右边每个点权值可以增大，要求使左边任意点不大于右边与它相关的点。
然后先将右边点全部增大使其满足要求，这构成初始状态，下面进行改进，即对左右进行减小。
左边点权值减小会使代价增加，右边权值减小代价减小，但是减小时要保证左边永远不大于右边，右边的点不小于初始值。
这样，如果右边某个点减小，所有与之相关的点都减小，否则左边与之相关点会大于它。
我们每次同时减小一些点，尽量使右边点与左边点数量差值大，这样代价减少量便大。
选择右边点时必须选择左边所有与之相关点，这就是闭合图（详见胡伯涛论文）
用网络流或二分图找出每次集体减小的点。
注意，每次必须找可减小的点中相等的且最大的点，将之减小到第二小的。
以上算法是本人乱搞的，国家队有人对此题做过详尽分析。
by captain @ 2016-10-14 20:45:14