這是最小樹形圖的題目，1是根節點，在開始的時候自己建圖。
輸入n，m;代表有n個結點，接下來n行給出結點的坐標。
接下來m行給出i,j兩個整數，代表i到j有連通，求出i到j的坐標距離，最後求最小樹形圖。
用朱劉算法可以解決。
代碼：
[cpp]
#include<iostream>
#include<algorithm>
#include<string.h>
#include<cmath>
using namespace std;
const int maxn=105;
#define INF 0x7fffffff
double map[maxn][maxn],visit[maxn];
int pt[maxn][2],n,pre[maxn];
double Dist(int i,int j)
{
return sqrt(pow(pt[i][0]-pt[j][0],2.0)+pow(pt[i][1]-pt[j][1],2.0));
}
void DFS(int u)
{
visit[u]=true;
for(int i=1; i<=n; i++)
if( !visit[i]&&map[u][i]<INF)
DFS(i);
}
bool Connected() //判斷是否連通，如果連通一定存在最小樹形圖。
{
memset(visit,false,sizeof(visit));
int i,cnt=0;
DFS(1);
for( i=1; i<=n; i++)
if( !visit[i])
return false;
return true;
}
double ZLEdmonds(){
int i,j,k;
bool circle[maxn];
double ans=0;
memset(circle,false,sizeof(circle));
while(true){
for(i=2;i<=n;i++){//找出最短弧集合E0
if(circle[i]) continue;
pre[i]=i;
map[i][i]=INF;
for(j=1;j<=n;j++){
if(circle[j]) continue;
if(map[j][i]<map[pre[i]][i])
pre[i]=j;
}
}
for(i=2;i<=n;i++){
if(circle[i]) continue;
j=i;
memset(visit,false,sizeof(visit));
while(!visit[j] && j!=1){
visit[j]=true;
j=pre[j];
}
if(j==1) continue; //檢查是否有環，能找到根節點說明沒環
i=j;
ans+=map[pre[i]][i];
for(j=pre[i];j!=i;j=pre[j]){ //i不用標記，用作後面縮點用
ans+=map[pre[j]][j];
circle[j]=true;
}
for(j=1;j<=n;j++){
if(circle[j]) continue;
if(map[j][i]!=INF)
map[j][i]-=map[pre[i]][i];
}
for(j=pre[i];j!=i;j=pre[j]) //將環中所有的點成點i，改變邊
for(k=1;k<=n;k++){
if(circle[k]) continue;
map[i][k]=min(map[i][k],map[j][k]);
if(map[k][j]!=INF)
map[k][i]=min(map[k][i],map[k][j]-map[pre[j]][j]);
}
break;
}
if(i>n){ //求出最小樹形圖的權值
for(j=2;j<=n;j++){
if(circle[j]) continue;
ans+=map[pre[j]][j];
}
break;
}
}
return ans;
}
int main()
{
int m,i,j;
while( scanf("%d%d",&n,&m)!=EOF){
for( i=1; i<=n; i++)
for( j=1; j<=n; j++)
map[i][j]=INF;
for( i=1; i<=n; i++)
scanf("%d%d",&pt[i][0],&pt[i][1]);
while( m--){
scanf("%d%d",&i,&j);
map[i][j]=Dist(i,j);
}
if( !Connected())
printf("poor snoopy\n");
else
printf("%.2lf\n",ZLEdmonds());
}
return 0;
}
