新单词unidirectional get T T
求有向图上，以某点为根的，最小生成树
参考别人的模板
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<iostream>
#include<algorithm>
#include<cmath>
#define inf 2000000000
using namespace std;
struct node1
{
double x,y;
}p[110];
struct node
{
int u,v;
double w;
}e[10010];
double ans,in[110];
int n,m,r,cnt,id[110],vis[110],pre[110];
int zhuliu(int r,int V,int E)
{
ans=0;
while(1)
{
int u,v,i;
//找最小入边
for(i=0;i<=V;i++)
in[i]=inf;
for(i=0;i<E;i++)
{
u=e[i].u;
v=e[i].v;
if(e[i].w<in[v] && u!=v)
{
pre[v]=u;
in[v]=e[i].w;
}
}
for(i=0;i<V;i++)//判断图不连通 直接返回
if(i!=r&&in[i]==inf) return -1;
//找环
cnt=0;//记缩点后的联通块编号
memset(id,-1,sizeof id);//id[i]表示i缩点后在哪个联通块
memset(vis,-1,sizeof vis);
in[r]=0;
for(i=0;i<V;i++)
{
// printf("i:%d ini:%.2lf\n",i,in[i]);
ans+=in[i];
v=i;
while(vis[v]!=i&&v!=r&&id[v]==-1)//找环
{
vis[v]=i;
v=pre[v];
}
if(v!=r&&id[v]==-1)//缩点
{
for(u=pre[v];u!=v;u=pre[u])
id[u]=cnt;
id[v]=cnt++;
}
}
if(cnt==0) break;//无环
//建新图
for(i=0;i<V;i++)
if(id[i]==-1) id[i]=cnt++;
for(i=0;i<E;i++)
{
u=e[i].u;
v=e[i].v;
e[i].u=id[u];
e[i].v=id[v];
if(id[u]!=id[v]) e[i].w-=in[v];
}
V=cnt;
r=id[r];
}
return 1;
}
int main()
{
int i,a,b;
while(~scanf("%d%d",&n,&m))
{
for(i=1;i<=n;i++)
scanf("%lf%lf",&p[i].x,&p[i].y);
for(i=0;i<m;i++)
{
scanf("%d%d",&a,&b);
e[i].u=a-1;
e[i].v=b-1;
if(a==b) e[i].w=inf;//除掉自环
else e[i].w=sqrt((p[a].x-p[b].x)*(p[a].x-p[b].x)+(p[a].y-p[b].y)*(p[a].y-p[b].y));
}
if(zhuliu(0,n,m)==1)
printf("%.2lf\n",ans);
else printf("poor snoopy\n");
}
return 0;
}