最小树形图
参考资料：
先翻译一部分上面的 Lecture notes：
最小树形图也就是有向最小生成树。如果有向加权图 G 有子图 T，T 中从某个结点 r 可以到达全部其他结点，并且若这些边是无向边，T 就是最小生成树的话，那么 T 就是 G 上以 r 为根的有向生成树。最小有向生成树就是有向生成树中边权值的和最小的那个。（有点晕。。）
引理 1.1 以下条件等价：
- T 是 G 的以 r 为根的有向生成树
- r 在 T 中的入度为 0，其它边在 T 中的入度是 1，且 T 是无环的。
- r 在 T 中的入度为 0，其它边在 T 中的入度是 1，T 中从 r 到其他任意结点都有有向路径
推论 1.2
设 T 是以 r 为根的有向生成树，设 (u,v) 是不在 T 中的一条边，且 v != r，u 不是 T 中 v 的后续结点（后续结点的意思是 T 中从 v 到 u 有路径），设 (u’, v) 是 T 中终点为 v 的（唯一的）边。那么把 T 加上 (u,v) 去掉 (u,v’) 仍然是一个 r 为根的有向生成树。
定理 4.1
设 G=（V, E, w）是加权有向图，设 r 在 V 中。设 C 是一个不包含 r 的由最小的入边构成的边集。那么，存在一个最小有向生成树，包含 C 中去掉一条边后剩余的边。
证明：设 T 是 G 中以 r 为根的最小有向生成树。设 v1 是 C 中的点，且 T 中从 r 到 v1 不经过 C 中其他的边。（一定至少存在一个点，比如 C 中在 T 上最接近 r 的点中的一个。）按照环上的顺序，设 v1, v2, .., vk 是 C 中的点。如果 (v1, v2), (v2, v3), …, (vk - 1, vk) 属于T，我们就搞定了。不过，假设存在某个 i < k，(v1, v2), (v2, v3), …, (vi - 1, vi) 属于 T，而 (vi, vi + 1) 不属于T。设 T 中 vi + 1 的入边为 (u, vi + 1)。vi 在 T 中的上游结点是 T 中从 r 到 v1 这些结点和 C 上的 v1, v2, …, vi - 1，所以 vi 不是 vi + 1 的下游结点（descendents…）。根据推论1.2，T 去掉 (u, vi + 1) 加上 (vi, vi + 1) 仍然是一个以 r 为根的生成树，记为T‘。既然 (vi, vi + 1) 是进入 vi + 1 的最短边，T’ 也是以 r 为根的最小有向生成树。一直这样做，我们就能构造一个以 r 为根，包含 C 中除了 (vk, v1) 之外所有边的最小有向生成树。
接下来说说做法，根据上面的定理：
- 找除了根节点外其他点的最小入边，如果哪个点没有，就说明无解
- 看看现在是否有环，如果无环则找到解了，记录当前选择的所有边的权值和，作为答案。
- 把环缩点，设 u 是不在环上的点，v 是在环上的点，minEdgeDis[v] 表示 v 的最短入边的权值，那么把边 (u, v) 的权值减去 minEdgeDis[v]。把环上所有的点合并为同一个点。回到第一步。
曾经2011年大连网络赛就出了这个算法的模板题 HDU 4009 Transfer Water，当时好像是 yds 远程过的…我到现在还没去做这道题。
comments powered by Disqus