【BZOJ 1937】[SHOI2004] Mst最小生成树

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=1937
神犇题解:https://blog.sengxian.com/solutions/bzoj-1937

解题报告

我们首先可以得到一个结论:$T$中的边的边权只会减少,其他边的边权只会增加
于是我们将$T$中的边放在左边,其他边放在右边,都作为二分图的点,点权为边权
然后左右两两连边,边权$v_i$为右边点的权值减左边点的权值

此时问题转化为,每一个点设一个$d_i$,满足二分图中任意一条边$i \to j$满足$v_{i \to j} \le d_i + d_j$,求最小化$\sum{d_i}$
这是$KM$算法的关键步骤。于是直接上$KM$算法就可以了

但我不会$KM$算法
←为什么这个频率这个鬼畜啊 QwQ

但不会$KM$算法我们也能做,回忆$KM$算法顶标的作用
最小的顶标和就是最大权匹配的权值和
于是我们用费用流增广这个二分图,直到增广到权值为负就可以了