题意：要求建立司令部到各个欧几里德平面上的节点，给定可建立的顶点对(u,v)  =  u 可建立单向信道至 v ，求司令部形成对所有节点的指挥需要的最小建设花费。
      算法：最小图形树，不解释~
 
 1/*
 2Problem: 3164        User: _mTy
 3Memory: 872K        Time: 172MS
 4Language: C++        Result: Accepted
 5
 6Source Code
 7*/
 8#include<cstdio>
 9#include <cstring>
10#include<cmath>
11#define MAXN 120
12#define inf 1000000000
13typedef double elem_t;
14elem_t edmonds(int n,elem_t mat[][MAXN*2],int* pre);
15int main(){
16    elem_t point[MAXN][2];
17    elem_t mat[MAXN*2][MAXN*2];
18    elem_t res,len;
19    int pre[MAXN];
20    int i,j,n,m,u,v;
21
22    while(scanf("%d%d",&n,&m)!=EOF){
23        for(i=0;i<n;i++) for(j=0;j<n;j++) mat[i][j]=inf;
24        for(i=0;i<n;i++) scanf("%lf%lf",&point[i][0],&point[i][1]);
25        for(i=0;i<m;i++){
26            scanf("%d%d",&u,&v); --u; --v;
27            len = pow(point[u][0]-point[v][0],2)+pow(point[u][1]-point[v][1],2);
28
29            len = sqrt(len);
30            mat[u][v]=len;
31        }
32
33        memset(pre,0,sizeof(pre));
34        pre[0]=-1;
35        res = edmonds(n,mat,pre);
36        if(res<0) printf("poor snoopy\n");
37        else printf("%.2f\n",res);
38    }
39    return 0;
40}
41
42//多源最小树形图,edmonds算法,邻接阵形式,复杂度O(n^3)
43//返回最小生成树的长度,构造失败返回负值
44//传入图的大小n和邻接阵mat,不相邻点边权inf
45//可更改边权的类型,pre[]返回树的构造,用父结点表示
46//传入时pre[]数组清零,用-1标出源点
47
48elem_t edmonds(int n,elem_t mat[][MAXN*2],int* pre){
49    elem_t ret=0;
50    int c[MAXN*2][MAXN*2],l[MAXN*2],p[MAXN*2],m=n,t,i,j,k;
51    for (i=0;i<n;l[i]=i,i++);
52    do{
53        memset(c,0,sizeof(c)),memset(p,0xff,sizeof(p));
54        for (t=m,i=0;i<m;c[i][i]=1,i++);
55        for (i=0;i<t;i++)
56            if (l[i]==i&&pre[i]!=-1){
57                for (j=0;j<m;j++)
58                    if (l[j]==j&&i!=j&&mat[j][i]<inf&&(p[i]==-1||mat[j][i]<mat[p[i]][i]))
59                        p[i]=j;
60                if ((pre[i]=p[i])==-1)
61                    return -1;
62                if (c[i][p[i]]){
63                    for (j=0;j<=m;mat[j][m]=mat[m][j]=inf,j++);
64                    for (k=i;l[k]!=m;l[k]=m,k=p[k])
65                        for (j=0;j<m;j++)
66                            if (l[j]==j){
67                                if (mat[j][k]-mat[p[k]][k]<mat[j][m])
68                                    mat[j][m]=mat[j][k]-mat[p[k]][k];
69                                if (mat[k][j]<mat[m][j])
70                                    mat[m][j]=mat[k][j];
71                            }
72                    c[m][m]=1,l[m]=m,m++;
73                }
74                for (j=0;j<m;j++)
75                    if (c[i][j])
76                        for (k=p[i];k!=-1&&l[k]==k;c[k][j]=1,k=p[k]);
77            }
78    }
79    while (t<m);
80    for (;m-->n;pre[k]=pre[m])
81        for (i=0;i<m;i++)
82            if (l[i]==m){
83                for (j=0;j<m;j++)
84                    if (pre[j]==m&&mat[i][j]==mat[m][j])
85                        pre[j]=i;
86                if (mat[pre[m]][m]==mat[pre[m]][i]-mat[pre[i]][i])
87                    k=i;
88            }
89    for (i=0;i<n;i++)
90        if (pre[i]!=-1)
91            ret+=mat[pre[i]][i];
92    return ret;
93}