http://poj.org/problem?id=3164
第一次做最小树形图，看着别人的博客写，还没弄懂具体的什么意思。
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define maxn 1000
using namespace std;
const int inf=<<; int n,m;
double g[maxn][maxn];
bool vis[maxn];
int cicl[maxn];
int pre[maxn];
struct node
{
double x,y;
}p[maxn]; double sqr(int x)
{
return x*x;
} double dis(int a,int b)
{
return sqrt(sqr(p[a].x-p[b].x)+sqr(p[a].y-p[b].y));
} void dfs(int s)
{
if(vis[s]) return ;
vis[s]=true;
for(int i=; i<=n; i++)
{
if(g[s][i]<inf)
{
dfs(i);
}
}
} bool deal()
{
dfs();
for(int i=; i<=n; i++)
{
if(!vis[i]) return false;
}
return true;
} double solve()
{
double ans=;
int i;
memset(cicl,,sizeof(cicl));
while()
{
for(i=; i<=n; i++)
{
if(cicl[i]) continue;
g[i][i]=inf;
pre[i]=i;
for(int j=; j<=n; j++)
{
if(cicl[j]) continue;
if(g[j][i]<g[pre[i]][i])
{
pre[i]=j;
}
}
}
int j;
for(i=; i<=n; i++)
{
if(cicl[i]) continue;
j=i;
memset(vis,false,sizeof(vis));
while(!vis[j]&&j!=)
{
vis[j]=true;
j=pre[j];
}
if(j==) continue;
i=j;
ans+=g[pre[i]][i];
for(j=pre[i]; j!=i; j=pre[j])
{
ans+=g[pre[j]][j];
cicl[j]=;
}
for(j=; j<=n; j++)
{
if(cicl[j]) continue;
if(g[j][i]<inf)
{
g[j][i]-=g[pre[i]][i];
}
}
for(j=pre[i]; j!=i; j=pre[j])
{
for(int k=; k<=n; k++)
{
if(cicl[k]) continue;
if(g[j][k]<inf)
{
g[i][k]=min(g[i][k],g[j][k]);
}
if(g[k][j]<inf)
{
g[k][i]=min(g[k][i],g[k][j]-g[pre[j]][j]);
}
}
}
break;
}
if(i>n)
{
for(j=; j<=n; j++)
{
if(cicl[j]) continue;
ans+=g[pre[j]][j];
}
break;
}
}
return ans;
} int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
for(int i=; i<=n; i++)
{
for(int j=; j<=n; j++)
{
g[i][j]=inf;
}
}
for(int i=; i<=n; i++)
{
scanf("%lf%lf",&p[i].x,&p[i].y);
}
for(int i=; i<m; i++)
{
int s,t;
scanf("%d%d",&s,&t);
g[s][t]=dis(s,t);
}
memset(vis,false,sizeof(vis));
if(!deal())
{
printf("poor snoopy\n");
}
else printf("%.2lf\n",solve());
}
return ;
}