何謂最小樹形圖，最小樹形圖，在一個有向圖中，定義某個節(jié)點為根節(jié)點，由該根節(jié)點擴展出來的一顆有向的生成樹，并且使這棵樹的權值最小。練習題
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. 除源點外，為其他所有節(jié)點Vi找一條權值最小的入邊，加入集合T。T就是最短邊的集合。加邊的方法：遍歷所有點到Vi的邊中權值最小的加入集合T，記pre[Vi]為該邊的起點，mincost[Vi]為該邊的權值。
3. 檢查集合T中的邊是否存在有向環(huán)，有則轉(zhuǎn)到步驟4，無則轉(zhuǎn)到步驟5。這里需要利用pre數(shù)組，枚舉檢查過的點作為搜索的起點，類似dfs的操作判斷有向環(huán)。
4. 將有向環(huán)縮成一個點。設環(huán)中有點{Vk1,Vk2,…,Vki}共i個點，用Vk代替縮成的點。在壓縮后的圖中，更新所有不在環(huán)中的點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中有向邊的權值總和就是最小樹形圖的權值總和。