图片均来自 y 总 /ww
树形图
- 无环
- 每个点的入度为 1 （除了 根 ）
朱刘算法
基于 贪心 算法
- 对于每个点（除了 根 ），找出所有入边中权值最小的边
-
选出的边中是否存在环 （无环，则结束算法，有环，则继续）
-
将所有的环缩点，构建一个新的图
对于边 （u - v）：
- 环内部，去掉
- 终点在环内，\(w = w_原 - w_{换上边}\)
- 其他边照搬
G -> G'
持续操作，直到退出
证明？
-
如果当前没有环，显然成立
-
如果有环
（1）至少去掉一条边
（2）必然存在一个最优解，使环上的边只去掉了一条（如果有超过两条，可以通过替换变成一条）