何谓最小树形图，最小树形图，在一个有向图中，定义某个节点为根节点，由该根节点扩展出来的一颗有向的生成树，并且使这棵树的权值最小。练习题
POJ3164，
1 #include<stdio.h>
2 #include<string.h>
3 #include<math.h>
4 #define MAXN 205
5 #define dis(x1,y1,x2,y2) (sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2)))
6 #define eps 1e-5
7 typedef double elem_t;
8 #define inf 1e10
9 double x[MAXN], y[MAXN];
10 double map[MAXN][MAXN];
11 int pre[MAXN];
12 int c[MAXN][MAXN], l[MAXN], p[MAXN];
13 elem_t edmonds(int n,elem_t mat[][MAXN],int* pre)
14 {
15 elem_t ret=0;
16 int m=n,t,i,j,k;
17 for (i=0;i<n;l[i]=i,i++);
18 do{
19 memset(c,0,sizeof(c));
20 memset(p,0xff,sizeof(p));
21
22 for (t=m,i=0;i<m;c[i][i]=1,i++);
23
24 for (i=0;i<t;i++)
25 if (l[i]==i&&pre[i]!=-1){
26 for (j=0;j<m;j++)
27 if (l[j]==j&&i!=j&&mat[j][i]+eps<inf&&(p[i]==-1||mat[j][i]<mat[p[i]][i]))
28 p[i]=j;
29 if ((pre[i]=p[i])==-1)
30 return -1;
31 if (c[i][p[i]]){
32 for (j=0;j<=m;mat[j][m]=mat[m][j]=inf,j++);
33 for (k=i;l[k]!=m;l[k]=m,k=p[k])
34 for(j=0;j<m;j++)
35 if(l[j]==j){
36 if(mat[j][k]-mat[p[k]][k]<mat[j][m])
37 mat[j][m]=mat[j][k]-mat[p[k]][k];
38 if(mat[k][j]<mat[m][j])
39 mat[m][j]=mat[k][j];
40 }
41 c[m][m]=1,l[m]=m,m++;
42 }
43 for (j=0;j<m;j++)
44 if (c[i][j])
45 for (k=p[i];k!=-1&&l[k]==k;c[k][j]=1,k=p[k]);
46 }
47 }
48 while (t<m);
49 for (;m-->n;pre[k]=pre[m])
50 for (i=0;i<m;i++)
51 if (l[i]==m){
52 for (j=0;j<m;j++)
53 if (pre[j]==m&&mat[i][j]==mat[m][j])
54 pre[j]=i;
55 if (mat[pre[m]][m]==mat[pre[m]][i]-mat[pre[i]][i])
56 k=i;
57 }
58 for (i=0;i<n;i++)
59 if (pre[i]!=-1)
60 ret+=mat[pre[i]][i];
61 return ret;
62 }
63
64 int main(){
65 int n, m;
66 int s, t;
67 while(scanf("%d%d",&n,&m)!=EOF){
68 for(int i = 0; i < n; i++){
69 scanf("%lf%lf",x+i,y+i);
70 }
71 for(int i = 0; i < MAXN; i++)
72 for(int j = 0; j < MAXN; j++)
73 map[i][j] = inf;
74 for(int i = 0; i < n; i++)
75 pre[i] = 0;
76
77 for(int i = 0; i < m; i++){
78 scanf("%d%d",&s,&t);
79 s--, t--;
80 map[s][t] = dis(x[s],y[s],x[t],y[t]);
81 }
82 pre[0]=-1;
83 double ans = edmonds(n,map,pre);
84 if(ans < 0)
85 printf("poor snoopy\n");
86 else
87 printf("%.2lf\n", ans);
88 }
89 return 0;
90 }
91
92 解决该问题的算法有两位中国人提出，有位同学将该论文总结一下：
最小树形图算法(Zhu-Liu Algorithm)：
1. 设最小树形图的总权值为cost，置cost为0。
2. 除源点外，为其他所有节点Vi找一条权值最小的入边，加入集合T。T就是最短边的集合。加边的方法：遍历所有点到Vi的边中权值最小的加入集合T，记pre[Vi]为该边的起点，mincost[Vi]为该边的权值。
3. 检查集合T中的边是否存在有向环，有则转到步骤4，无则转到步骤5。这里需要利用pre数组，枚举检查过的点作为搜索的起点，类似dfs的操作判断有向环。
4. 将有向环缩成一个点。设环中有点{Vk1,Vk2,…,Vki}共i个点，用Vk代替缩成的点。在压缩后的图中，更新所有不在环中的点V到Vk的距离：
map[V][Vk] = min {map[V][Vkj]-mincost[Vki]} 1<=j<=i；
map[Vk][V] = min {map[Vkj][V]} 1<=j<=I。
5. cost加上T中有向边的权值总和就是最小树形图的权值总和。