#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>

using namespace std;

const int INF=200000000;
const int maxn=120;
const int maxm=10010;

int n,m;
struct Point
{
	double x,y;
}p[maxn];

struct Edge
{
	int u,v;
	double cost;
}edge[maxm];

int pre[maxn],id[maxn],vis[maxn];
double in[maxn];

double zhuliu(int root,int n,int m)
{
	int u,v;
	double res=0.0;
	while(1)
	{
		for(int i=1;i<=n;++i)
			in[i]=INF;
		for(int i=0;i<m;++i)
			if(edge[i].u!=edge[i].v&&edge[i].cost<in[edge[i].v])
			{	
				pre[edge[i].v]=edge[i].u;
				in[edge[i].v]=edge[i].cost;
			}
		for(int i=1;i<=n;++i)
			if(i!=root&&in[i]==INF)
				return -1;//不存在最小树形图
		int tn=0;
		memset(id,-1,sizeof(id));
		memset(vis,-1,sizeof(vis));
		in[root]=0;
		for(int i=1;i<=n;++i)
		{	
			res+=in[i];
			v=i;
			while(vis[v]!=i&&id[v]==-1&&v!=root)
			{
				vis[v]=i;
				v=pre[v];
			}
			if(v!=root&&id[v]==-1)
			{
				for(int u=pre[v];u!=v;u=pre[u])
					id[u]=tn;
				id[v]=tn++;
			}
		}
		if(tn==0)
			break;//没有有向环
		for(int i=1;i<=n;++i)
			if(id[i]==-1)
				id[i]=tn++;
		for(int i=0;i<m;)
		{
			v=edge[i].v;
			edge[i].u=id[edge[i].u];
			edge[i].v=id[edge[i].v];
			if(edge[i].u!=edge[i].v)
				edge[i++].cost-=in[v];
			else
				swap(edge[i],edge[--m]);
		}
		n=tn;
		root=id[root];
	}
	return res;
}

double Distance(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 main()
{
	while(~scanf("%d%d",&n,&m))
	{
		for(int i=1;i<=n;++i)
			scanf("%lf%lf",&p[i].x,&p[i].y);
		int a,b;
		for(int i=0;i<m;++i)
		{
			scanf("%d%d",&a,&b);
			edge[i].u=a;
			edge[i].v=b;
			if(edge[i].u!=edge[i].v)
				edge[i].cost=Distance(a,b);
			else
				edge[i].cost=INF;
		}
		double ans=zhuliu(1,n,m);
		if(ans==-1)
			printf("poor snoopy\n");
		else
			printf("%.2f\n",ans);
	}
	return 0;
}

• Re:实在找不出来哪里错了，求大神指点 (2189) Commence 2015-10-26 20:14:44
  • Re:实在找不出来哪里错了，求大神指点 (133) Commence 2015-10-26 20:17:04
    • Re:实在找不出来哪里错了，求大神指点 (40) yaoyueduzhen 2016-05-11 20:16:01
    • Re:实在找不出来哪里错了，求大神指点 (15) 15310320305 2017-01-19 21:55:37