> #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:实在找不出来哪里错了，求大神指点 (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