最小树型图 [朱刘算法]

 1 /*
 2  * @Promlem: 
 3  * @Time Limit: ms
 4  * @Memory Limit: k
 5  * @Author: pupil-XJ
 6  * @Date: 2019-10-16 15:17:03
 7  * @LastEditTime: 2019-10-16 15:55:18
 8  */
 9 #include<cstdio>
10 #include<cmath>
11 #include<cstring>
12 #include<algorithm>
13 using namespace std;
14 const int INF = 0x3f3f3f3f;
15 const int MAXN = 1000+5;
16 const int MAXM = MAXN*MAXN;
17 
18 struct node {
19     int from, to;
20     double cost;
21 } edge[MAXM];
22 
23 int n, m;// n个点 m条有向边
24 int pre[MAXN];// 储存父节点
25 int vis[MAXN];// 标记作用
26 int id[MAXN];// id[i]记录节点i所在环的编号
27 double in[MAXN];// in[i]记录i入边最小的权值
28 
29 double zhuliu(int root) {
30     double res = 0;
31     while(1) {
32         for(int i = 0; i != n; ++i) in[i] = INF;
33         for(int i = 0; i != m; ++i) {
34             node e = edge[i];
35             if(e.from != e.to && e.cost < in[e.to]) {
36                 pre[e.to] = e.from;
37                 in[e.to] = e.cost;
38             }
39         }
40         for(int i = 0; i != n; ++i) 
41             if(i != root && in[i] == INF) 
42                 return -1;
43         int tn = 0;
44         memset(id, -1, sizeof(id));
45         memset(vis, -1, sizeof(vis));
46         in[root] = 0;
47         for(int i = 0; i != n; ++i) {
48             res += in[i];
49             int v = i;
50             while(vis[v] != i && id[v] == -1 && v != root) {
51                 vis[v] = i;
52                 v = pre[v];
53             }
54             if(v != root && id[v] == -1) {
55                 for(int u = pre[v]; u != v; u = pre[u]) id[u] = tn;
56                 id[v] = tn++;
57             }
58         }
59         if(tn == 0) break;
60         for(int i = 0; i != n; ++i) {
61             if(id[i] == -1) id[i] = tn++;
62         }
63         for(int i = 0; i != m; ++i) {
64             int v = edge[i].to;
65             edge[i].from = id[edge[i].from];
66             edge[i].to = id[edge[i].to];
67             if(edge[i].from != edge[i].to) edge[i].cost -= in[v];
68         }
69         n = tn;
70         root = id[root];
71     }
72     return res;
73 }
74 
75 int main() {
76     while(scanf("%d%d", &n, &m) == 2) {
77         double x[MAXN], y[MAXN];
78         for(int i = 0; i != n; ++i) scanf("%lf%lf", &x[i], &y[i]);
79         int s, e;
80         for(int i = 0; i != m; ++i) {
81             scanf("%d%d", &s, &e);
82             --s; --e;
83             edge[i].from = s;
84             edge[i].to = e;
85             edge[i].cost = sqrt((x[s]-x[e])*(x[s]-x[e])+(y[s]-y[e])*(y[s]-y[e]));
86         }
87         double ans = zhuliu(0);
88         if(ans == -1) printf("poor snoopy\n");
89         else printf("%.2lf\n", ans);
90     }
91     return 0;
92 }