朱刘算法(最小树形图).doc

朱刘算法(最小树形图).doc图论是ACM竞赛中比较重要的组成部分，其模型广泛存在于现实生活之中。因其表述 形象生动，思维方式抽象而不离具体， 因此深受各类喜欢使劲 YY的Acmer的喜爱。这篇文
章引述图论中有关有向图最小生成树的部分， 具体介绍朱刘算法的求解思路，图论是ACM竞赛中比较重要的组成部分，其模型广泛存在于现实生活之中。因其表述 形象生动，思维方式抽象而不离具体， 因此深受各类喜欢使劲 YY的Acmer的喜爱。这篇文
章引述图论中有关有向图最小生成树的部分， 具体介绍朱刘算法的求解思路， 并结合一系列
coding技巧，实现最小树型图 0 (VE)的算法，并在最后提供了该算法的模版，以供参考。
关于最小生成树的概念， 想必已然家喻户晓。 给定一个连通图，要求得到一个包含所有
顶点的树(原图的子图)，使之所构成的边权值之和最小。 在无向图中，由于边的无向性质，
所以求解变得十分容易，使用经典的 kruskal与prim算法已经足够解决这类问题。而在有
向图中，则定义要稍微加上一点约束， 即以根为起点，沿给定有向边，可以访问到所有的点，
并使所构成的边权值之和最小，于是问题开始变得不一样了，我们称之为最小树型图问题。
该问题是由朱永津与刘振宏在上个世纪 60年代解决的，值得一提的是，这 2个人现在仍
然健在，更另人敬佩的是，朱永津几乎可以说是一位盲人。 解决最小树型图的算法后来被称
作朱刘算法，也是当之无愧的。
首先我们来阐述下算法的流程： 算法一开始先判断从固定根开始是否可达所有原图中的
点，若不可，则一定不存在最小树形图。这一步是一个很随便的搜索，写多搓都行，不加废 话。第二步，遍历所有的边，从中找出除根结点外各点的最小入边，累加权值，构成新图。 接着判断该图是否存在环。若不存在，则该图便是所求最小树型图， 当前权为最小权。否则
对环缩点，然后回到第二步继续判断。
这里存在一系列细节上的实现问题，以确保能够达到 VE的复杂度。首先是查环，对于
新图来说只有n-1条入边，对于各条入边，其指向的顶点是唯一的，于是我们可以在边表中 添加from，表示该边的出发点，并考虑到如果存在环，则对环上所有边反向，环是显然同 构的，于是最多作V次dfs就能在新图中找到所有的环， 并能在递归返回时对顶点重标号进
行缩点，此步的重标号可以用 hash数组映射。然后就是重要的改边法，对于所有不在环上
的边，修改其权为 w-min(v) ，w为当前边权，min(v)为当前连接v点的最小边权。其数学 意义在于选择当前边的同时便放弃了原来的最小入边。我们可以知道，每次迭代选边操作 O(E)，缩点操作 O(V)，更新权操作 O(E)，至少使一个顶点归入生成树，于是能在 V-1步内
完成计算，其复杂度为 O(VE)。
以上为定根最小树型图， 对于无固定根最小树型图， 只要虚拟一个根连所有的点的权为
边权总和+1，最后的结果减去(边权+1)即可。另外对于求所定的根标号，只要搜索被选中 的虚边就可以判断了。
#in elude <cstdio>
#in elude <iostream>
#in elude <cmath>
#in elude <estri ng>
using n amespaee std;
con st int N=101,M=100