题意：
给定n个点 m条有向边（点标从1开始）
下面n个点坐标
下面m条边
问最小树形图权值（无则输出一句话）
思路：最小树形图裸题
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <math.h>
using namespace std;
/*
* 最小树形图
* 复杂度O(NM)
* 点从0开始
*/
const int INF = 0x3f3f3f3f;
const int MAXN = 1010;
const int MAXM = 40010;
struct Edge{
int u,v;
double cost;
}edge[MAXM];
int pre[MAXN],id[MAXN],visit[MAXN];
double in[MAXN];
double zhuliu(int root,int n,int m,Edge edge[])
{
int u,v;
double res=0;
while(1)
{
for(int i = 0;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 = 0;i < n;i++)
if(i != root && in[i] == INF)
return -1;//不存在最小树形图
int tn = 0;
memset(id,-1,sizeof(id));
memset(visit,-1,sizeof(visit));
in[root] = 0;
for(int i = 0;i < n;i++)
{
res += in[i];
v = i;
while( visit[v] != i && id[v] == -1 && v != root)
{
visit[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 = 0;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 dis[105][105];
struct node{
double x,y;
}p[105];
double Dis(node a, node b){return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}
int n, m;
int main()
{
int i, j, u, v; double d;
while(~scanf("%d %d", &n, &m)){
for(i = 0; i < n; i++)
{
scanf("%lf%lf",&p[i].x,&p[i].y);
for(j = 0; j < n; j++)dis[i][j] = INF;
}
while(m--){
scanf("%d%d",&u,&v); u--, v--;
dis[u][v] = min(dis[u][v], Dis(p[u],p[v]));
}
int edgenum = 0;
for(i = 0; i < n; i++)if(i!=j)
for(j = 0; j < n; j++)if(dis[i][j]<INF)
{
Edge E={i,j,dis[i][j]};
edge[edgenum++] = E;
}
d = zhuliu(0,n,edgenum,edge);
if(d<0)puts("poor snoopy");
else printf("%.2lf\n", d);
}
return 0;
}