題意：要求建立司令部到各個(gè)歐幾里德平面上的節(jié)點(diǎn)，給定可建立的頂點(diǎn)對(duì)(u,v) = u 可建立單向信道至 v ，求司令部形成對(duì)所有節(jié)點(diǎn)的指揮需要的最小建設(shè)花費(fèi)。
算法：最小圖形樹，不解釋~
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算法,鄰接陣形式,復(fù)雜度O(n^3)
43//返回最小生成樹的長(zhǎng)度,構(gòu)造失敗返回負(fù)值
44//傳入圖的大小n和鄰接陣mat,不相鄰點(diǎn)邊權(quán)inf
45//可更改邊權(quán)的類型,pre[]返回樹的構(gòu)造,用父結(jié)點(diǎn)表示
46//傳入時(shí)pre[]數(shù)組清零,用-1標(biāo)出源點(diǎn)
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}