所謂的最小樹形圖，就是讓你在一個有向圖中找一個根和由根擴展出來的一顆有向的生成樹，并且使這棵樹的權值最小。
令人欣喜的是，這個算法是由中國人提出來的，這也是我正式學習的第一個中國人提出來的算法^_^
最小樹形圖算法(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中有向邊的權值總和就是最小樹形圖的權值總和。
源代碼如下：(參考了網上的代碼）
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
#define INF 99999999
#define min( a, b ) ( (a)< (b)?(a): (b) )
struct point
{
double x;
double y;
}p[200];
int pre[200];//記錄該節點的前驅
double graph[200][200], ans;//圖數組和結果
bool visit[110], circle[110];//visit記錄該點有沒有被訪問過，circle記錄改點是不是在一個圈里
int n, m, root;//頂點數+邊數+根節點標號
void dfs( int t )//一個深度優先搜索，搜索出一個最大的聯通空間
{
int i;
visit[t]= true;
for(i= 1; i<= n; ++i )
{
if( !visit[i] && graph[t][i]!= INF )
dfs( i );
}
}
bool check()//這個函數用來檢查最小樹形圖是否存在，即如果存在，那么一遍dfs后，應該可以遍歷到所有的節點
{
memset( visit, false, sizeof(visit) );
dfs( root );
for( int i= 1; i<= n; ++i )
{
if( !visit[i] )
return false;
}
return true;
}
double dist( int i, int j )
{
return sqrt( (p[i].x-p[j].x)*(p[i].x-p[j].x)+(p[i].y-p[j].y)*(p[i].y-p[j].y) );
}
int exist_circle()//判斷圖中是不是存在有向圈
{
int i;
int j;
root= 1; pre[root]= root;
for(i= 1; i<= n; ++i )
{
if( !circle[i] && i!= root )
{
pre[i]= i; graph[i][i]= INF;
for(j= 1; j<= n; ++j )
{
if( !circle[j] && graph[j][i]< graph[pre[i]][i] )
pre[i]= j;
}
}
}//這個for循環負責找出所有非根節點的前驅節點
for( i= 1; i<= n; ++i )
{
if( circle[i] )
continue;
memset( visit, false, sizeof(visit) );
int j= i;
while( !visit[j] )
{
visit[j]= true;
j= pre[j];
}
if( j== root )
continue;
return j;
}//找圈過程，最后返回值是圈中的一個點
return -1;//如果沒有圈，返回-1
}
void update( int t )//縮圈之后更新數據
{
int i;
int j;
ans+= graph[pre[t]][t];
for(i=pre[t]; i!= t; i= pre[i] )
{
ans+= graph[pre[i]][i];
circle[i]= true;
}//首先把圈里的邊權全部加起來，并且留出t節點，作為外部接口
for(i= 1; i<= n; ++i )
if( !circle[i] && graph[i][t]!= INF )
graph[i][t]-= graph[pre[t]][t];
//上面這個for循環的作用是對t節點做更新操作，為什么要單獨做？你可以看看線面這個循環的跳出條件。
for(j= pre[t]; j!= t; j= pre[j] )
for( int i= 1; i<= n; ++i )
{
if( circle[i] )
continue;
if( graph[i][j]!= INF )
graph[i][t]= min( graph[i][t], graph[i][j]- graph[pre[j]][j] );
/**///////////////////////////////////////////////////////////////////////////
graph[t][i]= min( graph[j][i], graph[t][i] );
}
//這個循環對圈中的其他頂點進行更新
}
void solve()
{
int j;
memset( circle, false, sizeof(circle) );
while( ( j= exist_circle() )!= -1 )
update( j );
for( j= 1; j<= n; ++j )
if( j!= root && !circle[j] )
ans+= graph[pre[j]][j];
printf("%.2lf\n", ans );
}
int main()
{
int i;
while( scanf("%d%d",&n,&m)!= EOF )
{
for(i= 0; i<= n; ++i )
for( int j= 0; j<= n; ++j )
graph[i][j]= INF;
for(i= 1; i<= n; ++i )
scanf("%lf%lf",&p[i].x, &p[i].y );
for(i= 0; i< m; ++i )
{
int a, b;
scanf("%d%d",&a,&b);
graph[a][b]= dist( a, b );
}
root= 1;
ans= 0;
if( !check() )
printf("poor snoopy\n");
else
solve();
}
return 0;
}