CVBB ACM Team

/*
朱刘算法是干什么的呢
给定一个有向图以及点X，求以X为根节点的最小生成树（有向） 
*/ 
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
#define maxn 10005
using namespace std;
struct nod
{
	int x,y;
	double w;
	nod(){}
}edge[maxn];
int n,m,root;
double x[maxn],y[maxn];
int id[maxn],vis[maxn],pre[maxn];
double in[maxn];
double zhuliu()
{
	double ans=0;
	int sz=n;
	while(1)
	{
		for(int i=1;i⇐sz;i++)
			in[i]=123456789.0,vis[i]=id[i]=0;
		for(int i=1;i⇐m;i++)
		{
			if( edge[i].w<in[edge[i].y] && edge[i].x!=edge[i].y )
				pre[edge[i].y]=edge[i].x,in[edge[i].y]=edge[i].w;
		}
 
		in[root]=0.0;
 
		for(int i=1;i⇐sz;i++)
		{
			if(in[i]==123456789.0 && i!=root)
				return -1.0;
		}
		int cnt=0;
		for(int i=1;i⇐sz;i++)
		{
			ans+=in[i];
			int now=i;
			while(vis[now]!=i && !id[now] && now!=root)
			{
				vis[now]=i;
				now=pre[now];
			}
			if(now!=root && !id[now])
			{
				cnt++;
				id[now]=cnt;
				for(int j=pre[now];j!=now;j=pre[j])
					id[j]=cnt;
			}
		}
		if(!cnt)
			break;
		for(int i=1;i⇐sz;i++)
			if(!id[i])
				id[i]=++cnt;
		for(int i=1;i⇐m;i++)
		{
			int temp=edge[i].y;
			edge[i].x=id[edge[i].x];
			edge[i].y=id[edge[i].y];
			if(edge[i].x!=edge[i].y)
				edge[i].w-=in[temp];
		}
		sz=cnt;
		root=id[root];
	}
	return ans;
}
int main()
{
	while(~scanf(“%d%d”,&n,&m))
	{
		for(int i=1;i⇐n;i++)
			scanf(“%lf%lf”,&x[i],&y[i]);
		for(int i=1;i⇐m;i++)
		{
			int a,b;
			scanf(“%d%d”,&a,&b);
			edge[i].x=a; edge[i].y=b;
			if(a!=b)
				edge[i].w=sqrt((x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]));
			else
				edge[i].w=123456789;		
		}
		root=1;
		double res=zhuliu();
		if(res==-1.0)
			printf(“poor snoopy\n”);
		else
			printf(“%.2f\n”,res);
	}
}