題目連結： poj 3164
有向圖的最小樹形圖：此算法由朱永津和劉振宏在1965年發表。
膜拜--
寫下自己了解的思路--- 一天一道題----痛并快樂着--
解題步驟：
1》先從根節點DFS一下，看是否有解--
2》尋找除根節點外的所有點的最小入邊--
3》從所有點向上尋找--看中間路徑是否存在環--（如果不存在環，說明已經找到最小樹形圖--将各邊加入ans中--算法結束）
4》如果存在環的話就先将環上各邊之和加入ans--然後找各點的其他入邊并更新（因為已将最小入邊加上--其他入邊以後如果還用時就應該用它與最小入邊的內插補點）
---然後-收縮環為環中一點--除收縮點外，其他點與外界的狀态全部轉移到收縮點--其他點标記一下（隐藏）--然後傳回步驟2.
圖文可在百度文庫下載下傳：最小樹形圖
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m;
#define M 999999999
double x[120],y[120];
double map[120][120];
bool fafe[120];
double dist(int xx,int yy)
{
double lp=sqrt((x[xx]-x[yy])*(x[xx]-x[yy])+(y[xx]-y[yy])*(y[xx]-y[yy]));
return lp;
}
int fer[120];
double zhuliu()
{
int pre[120],i;
bool visit[120];
double ans=0;
for (int i=1;i<=n;i++)
{
fafe[i]=false;
map[i][i]=M;
}
pre[1]=1;
while (true)
{
for (i=2;i<=n;i++)
{
if (fafe[i])continue;
pre[i]=i;
for (int j=1;j<=n;j++)
{
if (!fafe[j]&&map[j][i]<map[pre[i]][i])
pre[i]=j;
}
}
for (i=2;i<=n;i++)
{
if (fafe[i])continue;
memset(visit,false,sizeof(visit));
visit[1]=true;
int j=i;
do
{
visit[j]=true;
j=pre[j];
}while(!visit[j]);
if (j==1) continue;//從根節點出發--到i之間無環。
i=j;/*這裡是i=j，，，寫成j=i就逾時--- 如果有環時j不是回到i了嗎？？
原來是從i想上找---循環可能沒有i---如：3——4---5----4：pre[3]=4--pre[4]=5---pre[5]=4;
這樣的話--如果下面的循環還是從i開始--但是判斷結果是就j！=i--永遠會不到3的位置--就會 Time Limit Exceeded*/
do
{
ans+=map[pre[j]][j];
j=pre[j];
}while (j!=i);
j=i;
do//改變權值
{
for (int k=1;k<=n;k++)
{
if (fafe[k]) continue;
if (map[k][j]<M&&k!=pre[j])
map[k][j]-=map[pre[j]][j];
}
j=pre[j];
}while (j!=i);
for (j=1;j<=n;j++)//将與環上的點相連的路全部連在i上
{
if (j==i) continue;
for (int k=pre[i];k!=i;k=pre[k])
{
if (map[k][j]<map[i][j]) map[i][j]=map[k][j];
if (map[j][k]<map[j][i]) map[j][i]=map[j][k];
}
}
for (j=pre[i];j!=i;j=pre[j])//除i點，其他點隐藏
fafe[j]=true;
break;// 此環已壓縮--當做一點--重新找每點的最短入邊--
}
if (i==n+1)//從2到n都無環---
{
for (int j=2;j<=n;j++)
if (!fafe[j])
ans+=map[pre[j]][j];
break;
}
}
return ans;
}
void DFS(int xx)
{
fafe[xx]=false;
for (int i=1;i<=n;i++)
if (fafe[i]&&map[xx][i]!=M)
DFS(i);
return ;
}
int main()
{
while (~scanf("%d%d",&n,&m))
{
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
map[i][j]=M;
for (int i=1;i<=n;i++)
scanf("%lf%lf",&x[i],&y[i]);
int a,b;
for (int i=0;i<m;i++)
{
scanf("%d%d",&a,&b);
if (a==b) continue;
map[a][b]=dist(a,b);
}
bool falg=true;
memset(fafe,true,sizeof(fafe));
DFS(1);
for (int i=1;i<=n;i++)
if (fafe[i])
{
falg=false;
break;
}
if (falg)
printf("%.2lf\n",zhuliu());
else
printf("poor snoopy\n");
}
return 0;
}