所謂的最小樹形圖，就是讓你在一個有向圖中找一個根和由根擴展出來的一顆有向的生成樹，并且使這棵樹的權(quán)值最小。
令人欣喜的是，這個算法是由中國人提出來的，這也是我正式學(xué)習(xí)的第一個中國人提出來的算法^_^
最小樹形圖算法(Zhu-Liu Algorithm)：
1. 設(shè)最小樹形圖的總權(quán)值為cost，置cost為0。
2. 除源點外，為其他所有節(jié)點Vi找一條權(quán)值最小的入邊，加入集合T。T就是最短邊的集合。加邊的方法：遍歷所有點到Vi的邊中權(quán)值最小的加入集合T，記pre[Vi]為該邊的起點，mincost[Vi]為該邊的權(quán)值。
3. 檢查集合T中的邊是否存在有向環(huán)，有則轉(zhuǎn)到步驟4，無則轉(zhuǎn)到步驟5。這里需要利用pre數(shù)組，枚舉檢查過的點作為搜索的起點，類似dfs的操作判斷有向環(huán)。
4. 將有向環(huán)縮成一個點。設(shè)環(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中有向邊的權(quán)值總和就是最小樹形圖的權(quán)值總和。
源代碼如下：(參考了網(wǎng)上的代碼）
#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];//記錄該節(jié)點的前驅(qū)
double graph[200][200], ans;//圖數(shù)組和結(jié)果
bool visit[110], circle[110];//visit記錄該點有沒有被訪問過，circle記錄改點是不是在一個圈里
int n, m, root;//頂點數(shù)+邊數(shù)+根節(jié)點標(biāo)號
void dfs( int t )//一個深度優(yōu)先搜索，搜索出一個最大的聯(lián)通空間
{
int i;
visit[t]= true;
for(i= 1; i<= n; ++i )
{
if( !visit[i] && graph[t][i]!= INF )
dfs( i );
}
}
bool check()//這個函數(shù)用來檢查最小樹形圖是否存在，即如果存在，那么一遍dfs后，應(yīng)該可以遍歷到所有的節(jié)點
{
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循環(huán)負(fù)責(zé)找出所有非根節(jié)點的前驅(qū)節(jié)點
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 )//縮圈之后更新數(shù)據(jù)
{
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;
}//首先把圈里的邊權(quán)全部加起來，并且留出t節(jié)點，作為外部接口
for(i= 1; i<= n; ++i )
if( !circle[i] && graph[i][t]!= INF )
graph[i][t]-= graph[pre[t]][t];
//上面這個for循環(huán)的作用是對t節(jié)點做更新操作，為什么要單獨做？你可以看看線面這個循環(huán)的跳出條件。
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] );
}
//這個循環(huán)對圈中的其他頂點進行更新
}
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;
}