Writing /data/wiki/data/cache/d/de2edb2fcb553ea79b79c722a4e13dbc.captchaip failed
/*
朱刘算法是干什么的呢
给定一个有向图以及点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);
}
}