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