最小树形图（有向图最小生成树）
无向图的最小生成树可以使用Kruskal或者Prim算法。
但是这两种放在有向图中都不适用，首先Kruskal算法直接取边，没有要求边的方向，会导致某些点无法到达。如：
按照Kruskal算法，取1 1 2三条边，点3就是无法到达的（没有入边）。
Prim算法在下面这个样例失效了。以1为根：
正解为9 4 1，和为14，Prim一昧追求最小边，选择了9 4 2，和为15。
朱刘算法
朱刘算法是1965年朱永津和刘振宏提出的复杂度为O(VE)的算法。
便于理解先说说朱刘算法的步骤。
- ①除了根，每个顶点找到一个最小入边，组成一个图。其中根必定是孤立点（没有入度），若还存在孤立点（没有入度），则最小树形图不存在。
- ②查找组成的图中是否存在环，若不存在，则此图为最小树形图。否则转向③。
- ③将环收缩为点，并调整边权，然后转向①。
变量
- root：根节点
- cnt：现在的图中有几个环
- in数组：每个点的最小输入的权值。
- pre数组：每个点的最小入边的起点。
- vis数组：是否已经遍历过该点（查环时使用）。
- id数组：每个点所属环的编号。
①
简便方法是先将每个点的in的权值设为无穷大，遍历每条边，若边的终点的in大于此边的权值，则将此边的pre设为该边的起点，并更新in为该边的权值。
②
由①的方法选出n-1条边（根节点没有选入边），若组成的图中无环，则n-1条边连接n个点，就是最小树形图。若有环，则必定不能连接n个点（m个点成环需要m条边，成链只需要m-1条边）。其中没有被连接的点也必定是root。（其他点没有被连接说明是孤立点，最小树形图不存在。）组成的环也必定是没有伸进来的”手臂”的环，但是可以有伸出去的”手臂”。(如上图 图b)
如何查环呢。
对每一个点寻找父亲，再寻找父亲的父亲，同时记录走过的点。若走到了一个已经经过的点，则该点必在环中，从该点开始遍历父亲，就能找到整个环，并标记环中点属于哪个环（更新id为cnt(第几个环)）。同时，更新完这个环之后cnt++。
若查环结束，cnt==0，则退出，最小树形图已经找到。否则继续。
然后更新不在环中的点的id为cnt，同时cnt++。用于缩点和调整边权。
③
如何缩点呢。
将每条边（所有边，不仅仅是第①步中选出的边）的起点和终点更改为id，也就是说，每条边都变成了连接环或单点的边，环内的边变成了由环到环的边，相当于自环，（A→A），自环在第①步中是不予考虑的。相当于重新构图了，图中仅剩下环外的边。
接下来考虑调整边权和统计最小树形图的边权之和。
假设第一次进行第①步后，选中以下三条蓝边。
红点为根节点。此时我们要尝试选中红色的边，就要将2号点的入边取消选中。那么选中红边的代价为2-1（选中红边代价+2，取消选中2号点的入边代价-1）。也就是说，我们在已经选中的边的基础上，再选中一条边，代价为w-in[v]（w为要选中边的权值，v为边指向的点）。
那我我们在第一次选边的时候，统计选中的边的权值的和。此后选中另一条边（环外的边），新增代价为w-in[v]。那么我们在缩点之后，将所有环外的边的边权改为w-in[v]，那么下次选中该边，只需增加w-in[v]的代价。
更新环数为点数（环都被缩为点啦），然后跳回①继续循环。
代码（看不懂的瞅瞅代码）
#include<cstdio>
#include<iostream>
using namespace std;
const int N = 1005, INF = 0x7fffffff;
struct Edge {
int x, y;
int w;
}edge[N];
int vis[N];
int id[N];//结点所属环编号
int in[N], pre[N];//in[]为最小入边权,pre[]为其对应的起点
int zhuLiu(int root, int n, int m) {//root结点、点数、边数
int res = 0;//最小树形图总权值
while (true) {
for (int i = 0; i < n; i++)//初始化为无穷大
in[i] = INF;
//寻找每个点的最小入边
for (int i = 0; i < m; i++) {//遍历每条边
int x = edge[i].x;
int y = edge[i].y;
if (edge[i].w < in[y] && x != y) {//更新最小入边，忽略自环
pre[y] = x;//记录前驱
in[y] = edge[i].w;//更新
}
}
//判断是否存在最小树形图(有无孤立点)
for (int i = 0; i < n; i++) {
if (i == root)
continue;
if (in[i] == INF)//除根节点外的点存在孤立点
return -1;
}
//寻找所有的环
int cnt = 0;//记录环数
in[root] = 0;
memset(id, -1, sizeof(id));
memset(vis, -1, sizeof(vis));
for (int i = 0; i < n; i++) {//标记每个环
res += in[i];//记录权值
int y = i;
while (vis[y] != i && id[y] == -1 && y != root) {//寻找图中有向环
//三种情况会终止：找到出现同样标记的点、结点已属其他环、遍历到根
vis[y] = i;//标记
y = pre[y];//向上找
}
if (y != root && id[y] == -1) {//没有遍历到根或没有找到结点属于其他环,说明找到有向环
for (int x = pre[y]; x != y; x = pre[x])//标记结点x为第几个环
id[x] = cnt;//记录结点所属环号
id[y] = cnt++;//记录结点所属环号并累加
}
}
if (cnt == 0)//无环，最小生成树找到
break;
for (int i = 0; i < n; i++)//可能存在环外的非孤立点（在链上）
if (id[i] == -1)//环数累加
id[i] = cnt++;
//建立新图,缩点重新标记
for (int i = 0; i < m; i++) {
int x = edge[i].x;
int y = edge[i].y;
edge[i].x = id[x];
edge[i].y = id[y];
if (id[x] != id[y])//两点不在同一环内,更新边权值
edge[i].w -= in[y];//x到y的距离为边权-in[y]
}
n = cnt;//以环数为下次操作的点数,继续上述操作,直到无环
root = id[root];//重新编号
}
return res;
}
int main() {
int n, m;//n个点m条有向边
scanf("%d%d", &n, &m);
for (int i = 0; i < m; i++) {//建图
scanf("%d%d%d", &edge[i].x, &edge[i].y, &edge[i].w);
if (edge[i].x == edge[i].y)//除去自环,即点到自身距离为INF（可省略）
edge[i].w = INF;
}
int res = zhuLiu(0, n, m);
if (res == -1)
printf("No\n");
else
printf("%d\n", res);
return 0;
}Tips：从1开始计数的话，抄模板会wa，bug在利用cnt重新编号这一块。
Views: 116