[kuangbin带你飞]之'最小生成树 '专题

带飞网址: https://vjudge.net/article/187

专题六：

√ POJ 1251 Jungle Roads
√ POJ 1287 Networking
√ POJ 2031 Building a Space Station
√ POJ 2421 Constructing Roads
ZOJ 1586 QS Network
√ POJ 1789 Truck History
√ POJ 2349 Arctic Network
POJ 1751 Highways
√ POJ 1258 Agri-Net
POJ 3026 Borg Maze
√ POJ 1679 The Unique MST
√ HDU 1233 还是畅通工程
√ HDU 1301 Jungle Roads
√ HDU 1875 畅通工程再续

// poj 1251

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 using namespace std;
 5 
 6 int n;
 7 int p[300];
 8 
 9 struct node {
10     char x, y;
11     int len;
12 } edge[100];
13 
14 int cmp(node a, node b) { return a.len < b.len; }
15 int find(int x) { return p[x] == x ? x : p[x] = find(p[x]); }
16 
17 int main() {
18     while(scanf("%d", &n) == 1 && n) {
19         char s[10], e[10];
20         int m, v, k, ans;
21         k = 0;
22         ans = 0;
23         for(int i = 0; i != 300; ++i) { p[i] = i; }
24 
25         for(int i = 0; i != n-1; ++i) {
26             scanf("%s%d", s, &m);
27             for(int j = 0; j != m; ++j) {
28                 scanf("%s%d", e, &v);
29                 edge[k].x = s[0];
30                 edge[k].y = e[0];
31                 edge[k].len = v;
32                 k++;
33             }
34         }
35         sort(edge, edge+k, cmp);
36         for(int i = 0; i != k; ++i) {
37             int x = find(edge[i].x);
38             int y = find(edge[i].y);
39             if(x != y) {
40                 ans += edge[i].len;
41                 p[x] = y;
42             }
43         }
44         printf("%d
", ans);
45     }
46     return 0;
47 }
View Code

// hdu 1278

 1 /*
 2  * @Promlem: 
 3  * @Time Limit: 1000ms
 4  * @Memory Limit: 10000k
 5  * @Author: pupil-XJ
 6  * @Date: 2019-10-13 23:15:47
 7  * @LastEditTime: 2019-10-13 23:30:02
 8  */
 9 #include<cstdio>
10 #include<iostream>
11 #include<algorithm>
12 using namespace std;
13 const int MAXN = 50000+5;
14 
15 struct node {
16     int s, e;
17     int len;
18     bool operator < (const node &a) const {
19         return len < a.len;
20     }
21 } edge[MAXN];
22 
23 int n, m;
24 int fa[MAXN];
25 inline int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }
26 
27 inline int krustra() {
28     int cnt = 1, sum = 0;
29     sort(edge, edge+m);
30     for(int i = 1; i <= n; ++i) fa[i] = i;
31     for(int i = 0; i != m; ++i) {
32         int xf = find(edge[i].s);
33         int yf = find(edge[i].e);
34         if(xf != yf) {
35             sum += edge[i].len;
36             ++cnt;
37             fa[xf] = yf;
38         }
39         if(cnt == n) break;
40     }
41     return sum;
42 }
43 
44 int main() {
45     ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
46     
47     int x, y;
48     while(scanf("%d", &n) == 1 && n && scanf("%d", &m) == 1) {
49         for(int i = 0; i != m; ++i) cin >> edge[i].s >> edge[i].e >> edge[i].len;
50         cout << krustra() << "
";
51     }
52     return 0;
53 }
View Code

// poj 2031

 1 /*
 2  * @Promlem: 
 3  * @Time Limit: ms
 4  * @Memory Limit: k
 5  * @Author: pupil-XJ
 6  * @Date: 2019-10-13 23:40:24
 7  * @LastEditTime: 2019-10-14 00:08:52
 8  */
 9 #include<iostream>
10 #include<cmath>
11 #include<algorithm>
12 #include<iomanip>
13 using namespace std;
14 const int MAXN = 10000+5;
15 
16 struct node {
17     int s, e;
18     double len;
19     bool operator < (const node &a) const {
20         return len < a.len;
21     }
22 } edge[MAXN];
23 int n, cnt;
24 double x[MAXN], y[MAXN], z[MAXN], r[MAXN];
25 inline double getlen(int i, int j) {
26     double len = sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])+(z[i]-z[j])*(z[i]-z[j])) - r[i] - r[j];
27     if(len < 0) return 0.0;
28     return len;
29 }
30 
31 int fa[MAXN];
32 inline int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }
33 
34 inline double krustra() {
35     int num = 1;
36     double sum = 0;
37     sort(edge, edge+cnt);
38     for(int i = 1; i <= n; ++i) fa[i] = i;
39     for(int i = 0; i != cnt; ++i) {
40         int xf = find(edge[i].s);
41         int yf = find(edge[i].e);
42         if(xf != yf) {
43             sum += edge[i].len;
44             ++num;
45             fa[xf] = yf;
46         }
47         if(num == n) break;
48     }
49     return sum;
50 }
51 
52 int main() {
53     ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
54     cout.setf(ios::fixed);
55     while(cin >> n && n) {
56         for(int i = 1; i <= n; ++i) cin >> x[i] >> y[i] >> z[i] >> r[i];
57         cnt = 0;
58         for(int i = 1; i <= n-1; ++i) {
59             for(int j = i+1; j <= n; ++j) {
60                 edge[cnt].s = i; edge[cnt].e = j;
61                 edge[cnt].len = getlen(i, j);
62                 ++cnt;
63             }
64         }
65         cout << fixed << setprecision(3) << krustra() << "
";
66     }
67     return 0;
68 }
View Code

// poj 2421

 1 /*
 2  * @Promlem: 
 3  * @Time Limit: ms
 4  * @Memory Limit: k
 5  * @Author: pupil-XJ
 6  * @Date: 2019-10-14 00:31:28
 7  * @LastEditTime: 2019-10-14 01:15:20
 8  */
 9 #include<iostream>
10 #include<algorithm>
11 using namespace std;
12 const int MAXN = 100+5;
13 
14 struct node {
15     int s, e;
16     int len;
17     bool operator < (const node &a) const {
18         return len < a.len;
19     }
20 } edge[MAXN*MAXN];
21 
22 int n, m, ans;
23 int G[MAXN][MAXN];
24 int fa[MAXN];
25 
26 int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }
27 
28 int krustra() {
29     int cnt = 1;
30     int sum = 0;
31     sort(edge, edge+ans);
32     for(int i = 1; i <= n; ++i) fa[i] = i;
33     for(int i = 0; i != ans; ++i) {
34         int xf = find(edge[i].s);
35         int yf = find(edge[i].e);
36         if(xf != yf) {
37             sum += edge[i].len;
38             ++cnt;
39             fa[xf] = yf;
40         }
41         if(cnt == n) break;
42     }
43     return sum;
44 }
45 
46 int main() {
47     ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
48     cin >> n;
49     ans = 0;
50     for(int i = 1; i <= n; ++i) {
51         for(int j = 1; j <= n; ++j) {
52             cin >> G[i][j];
53             if(j > i) {
54                 edge[ans].s = i; edge[ans].e = j;
55                 edge[ans].len = G[i][j];
56                 ++ans;
57             }
58         }
59     }
60     cin >> m;
61     int x, y, sum = 0;
62     for(int i = 0; i != m; ++i) {
63         cin >> x >> y;
64         if(x > y) swap(x, y);
65         for(int i = 0; i != ans; ++i) {
66             if(edge[i].s == x && edge[i].e == y) {
67                 edge[i].len = 0;
68                 break;
69             }
70         }
71     }
72     // cout << krustra() << endl;
73     // cout << sum << endl;
74     cout << krustra() - sum << "
";
75     return 0;
76 }
View Code

// poj 1789

 1 /*
 2  * @Promlem: 
 3  * @Time Limit: ms
 4  * @Memory Limit: k
 5  * @Author: pupil-XJ
 6  * @Date: 2019-10-15 12:16:19
 7  * @LastEditTime: 2019-10-15 12:45:59
 8  */
 9 #include<iostream>
10 using namespace std;
11 const int MAXN = 2000+5;
12 const int INF = 0x3f3f3f3f;
13 
14 int n, m;
15 int G[MAXN][MAXN];
16 char arr[MAXN][10];
17 
18 int vis[MAXN], dis[MAXN];
19 inline void prim() {
20     int sum = 0;
21     for(int i = 0; i != n; ++i) {
22         dis[i] = G[i][0];
23         vis[i] = 0;
24     }
25     vis[0] = 1;
26     for(int i = 0; i != n-1; ++i) {
27         int minn = INF;
28         int t;
29         for(int j = 0; j != n; ++j) {
30             if(!vis[j] && dis[j] < minn) {
31                 minn = dis[j];
32                 t = j;
33             }
34         }
35         sum += minn;
36         vis[t] = 1;
37         for(int j = 0; j != n; ++j) {
38             if(!vis[j] && dis[j] > G[t][j]) {
39                 dis[j] = G[t][j];
40             }
41         }
42     }
43     cout << "The highest possible quality is 1/" << sum << ".
";
44 }
45 
46 int main() {
47     ios::sync_with_stdio(false);
48     cin.tie(0); cout.tie(0);
49     while(cin >> n && n) {
50         int sum;
51         for(int i = 0; i != n; ++i) {
52             cin >> arr[i];
53             for(int j = 0; j <= i; ++j) {
54                 sum = 0;
55                 for(int k = 0; k != 7; ++k) {
56                     if(arr[j][k] != arr[i][k]) ++sum;
57                 }
58                 G[i][j] = G[j][i] = sum;
59             }
60             G[i][i] = INF;
61         }
62         prim();
63     }
64     return 0;
65 }
View Code

// poj 2349

 1 /*
 2  * @Promlem: 
 3  * @Time Limit: ms
 4  * @Memory Limit: k
 5  * @Author: pupil-XJ
 6  * @Date: 2019-10-15 15:37:50
 7  * @LastEditTime: 2019-10-15 17:12:29
 8  */
 9 #include<cstdio>
10 #include<cmath>
11 #include<algorithm>
12 using namespace std;
13 const int MAXN = 500+5;
14 
15 struct node {
16     int s, e;
17     double len;
18     bool operator < (const node &a) const {
19         return len < a.len;
20     }
21 } edge[MAXN*MAXN+5];
22 
23 int m, n, cnt;
24 int x[MAXN], y[MAXN];
25 
26 int fa[MAXN];
27 inline int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }
28 
29 inline void krustra() {
30     double x;
31     int ans = m;
32     for(int i = 1; i <= n; ++i) fa[i] = i;
33     for(int i = 0; i != cnt; ++i) {
34         int xf = find(edge[i].s);
35         int yf = find(edge[i].e);
36         if(xf != yf) {
37             fa[xf] = yf;
38             x = edge[i].len;
39             ++ans;
40         }
41         if(ans == n) break;
42     }
43     printf("%.2lf
", x);
44 }
45 
46 int main() {
47     int T;
48     scanf("%d", &T);
49     while(T--) {
50         cnt = 0;
51         scanf("%d%d", &m, &n);
52         for(int i = 1; i <= n; ++i) {
53             scanf("%d%d", &x[i], &y[i]);
54             for(int j = i-1; j >= 1; --j) {
55                 edge[cnt].s = i; edge[cnt].e = j;
56                 edge[cnt].len = sqrt((double)((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])));
57                 ++cnt;
58             }
59         }
60         sort(edge, edge+cnt);
61         krustra();
62     }
63     return 0;
64 }
View Code

// poj 1258

 1 /*
 2  * @Promlem: 
 3  * @Time Limit: ms
 4  * @Memory Limit: k
 5  * @Author: pupil-XJ
 6  * @Date: 2019-10-15 17:18:51
 7  * @LastEditTime: 2019-10-15 17:27:41
 8  */
 9 #include<iostream>
10 using namespace std;
11 const int MAXN = 100+5;
12 const int INF = 0x3f3f3f3f;
13 
14 int n;
15 int G[MAXN][MAXN];
16 int dis[MAXN], vis[MAXN];
17 
18 inline void prim() {
19     int sum = 0;
20     for(int i = 0; i != n; ++i) {
21         vis[i] = 0;
22         dis[i] = G[i][0];
23     }
24     vis[0] = 1;
25     for(int i = 0; i != n-1; ++i) {
26         int minn = INF;
27         int t;
28         for(int j = 0; j != n; ++j) {
29             if(!vis[j] && dis[j] < minn) {
30                 minn = dis[j];
31                 t = j;
32             }
33         }
34         sum += minn;
35         vis[t] = 1;
36         for(int j = 0; j != n; ++j) {
37             if(!vis[j] && dis[j] > G[t][j]) {
38                 dis[j] = G[t][j];
39             }
40         }
41     }
42     cout << sum << endl;
43 }
44 
45 int main() {
46     ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
47     while(cin >> n) {
48         for(int i = 0; i != n; ++i) {
49             for(int j = 0; j != n; ++j) {
50                 cin >> G[i][j];
51             }
52             G[i][i] = INF;
53         }
54         prim();
55     }
56     return 0;
57 }
View Code

// poj 1679

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<algorithm>
  4 using namespace std;
  5 
  6 struct Edge {
  7     int s, e;
  8     int w;
  9     int flag;
 10     int used;
 11     int del;
 12 }edges[10005];
 13 
 14 bool first;
 15 int n, m, cnt;
 16 
 17 bool cmp(const Edge& a, const Edge& b) {
 18     return a.w < b.w;
 19 }
 20 
 21 int p[1005];
 22 int find(int x) { return p[x] == x ? x : p[x] = find(p[x]); }
 23 
 24 int kruskal() {
 25     int ans = 0;
 26     cnt = 1;
 27     for(int i = 0; i != n; ++i) p[i] = i;
 28     for(int i = 0; i != m; ++i) {
 29         if(edges[i].del) continue;
 30         int x = find(edges[i].s);
 31         int y = find(edges[i].e);
 32         if(x != y) {
 33             ans += edges[i].w;
 34             p[x] = y;
 35             cnt++;
 36             if(first) edges[i].used = 1;
 37         }
 38         if(cnt == n) break;
 39     }
 40     return ans;
 41 }
 42 
 43 int main() {
 44     int T;
 45     scanf("%d", &T);
 46     while(T--) {
 47         scanf("%d%d", &n, &m);
 48         if(m == 0) {
 49             printf("0
");
 50             continue;
 51         }
 52         int x, y;
 53         for(int i = 0; i != m; ++i) {
 54             scanf("%d%d%d", &edges[i].s, &edges[i].e, &edges[i].w);
 55             edges[i].flag = edges[i].del = edges[i].used = 0;
 56             edges[i].s--;
 57             edges[i].e--;
 58         }
 59         sort(edges, edges+m, cmp);
 60         for(int i = 1; i <= m-1; ++i) if(edges[i].w == edges[i-1].w) edges[i].flag = edges[i-1].flag = 1;
 61         // int ans = 0;
 62         // for(int i = 0; i != m; ++i) {
 63         //     if(edges[i].flag) ans++;
 64         // }
 65         // printf("%d
", ans);
 66         first = true;
 67         int ans1 = kruskal();
 68         first = false;
 69         if(cnt != n) {
 70             printf("Not Unique!
");
 71             continue;
 72         }
 73         //printf("%d
", ans1);
 74         bool have = false;
 75         for(int i = 0; i != m; ++i) {
 76             if(edges[i].used && edges[i].flag) {
 77                 have = true;
 78                 break;
 79             }
 80         }
 81         if(!have) {
 82             printf("%d
", ans1);
 83             continue;
 84         }
 85         bool unique_ = true;
 86         for(int i = 0; i != m; ++i) {
 87             if(edges[i].used && edges[i].flag) {
 88                 edges[i].del = 1;
 89                 int ans2 = kruskal();
 90                 if(ans1 == ans2 && cnt == n) {
 91                     unique_ = false;
 92                     break;
 93                 }
 94                 edges[i].del = 0;
 95             }
 96         }
 97         if(!unique_) printf("Not Unique!
");
 98         else printf("%d
", ans1);
 99     }
100     return 0;
101 }
View Code

// hdu 1301

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 using namespace std;
 5 
 6 int n;
 7 int p[300];
 8 
 9 struct node {
10     char x, y;
11     int len;
12 } edge[100];
13 
14 int cmp(node a, node b) { return a.len < b.len; }
15 int find(int x) { return p[x] == x ? x : p[x] = find(p[x]); }
16 
17 int main() {
18     while(scanf("%d", &n) == 1 && n) {
19         char s, e;
20         int m, v, k, ans;
21         k = 0;
22         ans = 0;
23         for(int i = 0; i != 300; ++i) { p[i] = i; }
24 
25         for(int i = 0; i != n-1; ++i) {
26             getchar();
27             scanf("%c%d", &s, &m);
28             for(int j = 0; j != m; ++j) {
29                 getchar();
30                 scanf("%c%d", &e, &v);
31                 edge[k].x = s;
32                 edge[k].y = e;
33                 edge[k].len = v;
34                 k++;
35             }
36         }
37         sort(edge, edge+k, cmp);
38         for(int i = 0; i != k; ++i) {
39             int x = find(edge[i].x);
40             int y = find(edge[i].y);
41             if(x != y) {
42                 ans += edge[i].len;
43                 p[x] = y;
44             }
45         }
46         printf("%d
", ans);
47     }
48     return 0;
49 }
View Code

// hdu 1233 

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 using namespace std;
 5 #define MAX 110
 6 struct p{
 7     int start, end;
 8     int weight;
 9 }s[5000];
10 
11 int f[MAX];
12 
13 int cmp(const p & a, const p & b){
14     return a.weight < b.weight;
15 }
16 
17 int find(int x){
18     int r = x, tmp;
19     if(x == f[x]){
20         return x;
21     }
22     while(r != f[r]){
23         r = f[r];
24     }
25     while(x != r){
26         tmp = f[x];
27         f[x] = r;
28         x = tmp;
29     }
30     return r;
31 }
32 
33 int main()
34 {
35     int n, m;
36     while(cin >> n){
37         if(n == 0)break;
38         m = n*(n-1)/2;
39         for(int i = 0; i != m; ++i){
40             scanf("%d%d%d", &s[i].start, &s[i].end, &s[i].weight);
41         }
42         for(int i = 1; i <= n; ++i){
43             f[i] = i;
44         }
45         sort(s, s+m, cmp);
46         int sum = 0;
47         int k = 1;
48         int ans = 0;
49         while(k < n){
50             int i = find(s[ans].start);
51             int j = find(s[ans].end);
52             if(i != j){
53                 f[j] = i;
54                 sum += s[ans].weight;
55                 k++;
56             }
57             ++ans;
58         }
59         printf("%d
", sum);
60     }
61     return 0;
62 }
View Code

// hdu 1875

 1 #include<cstdio>
 2 #include<cmath>
 3 
 4 const double INF = 100005.0;
 5 
 6 struct island {
 7     int x, y;
 8 } p[105];
 9 
10 int n;
11 
12 double getdis(int a, int b) {
13     int x = p[a].x - p[b].x;
14     int y = p[a].y - p[b].y;
15     return sqrt((double)(x*x + y*y));
16 }
17 
18 double dis[105];
19 int vis[105];
20 void prim() {
21     double sum = 0.0;
22     int cnt = 1;
23     for(int i = 0; i != n; ++i) {
24         dis[i] = getdis(0, i);
25         if(dis[i] < 10.0 || dis[i] > 1000.0) dis[i] = INF;
26         vis[i] = 0;
27     }
28     vis[0] = 1;
29     for(int i = 0; i != n-1; ++i) {
30         double minn = INF;
31         int t = -1;
32         for(int j = 0; j != n; ++j) {
33             if(!vis[j] && dis[j] < minn) {
34                 minn = dis[j];
35                 t = j;
36             }
37         }
38         if(t == -1) break;
39         vis[t] = 1;
40         cnt++;
41         sum += minn;
42         for(int j = 0; j != n; ++j) {
43             if(!vis[j] && dis[j] > getdis(t, j) && getdis(t, j) >= 10.0 && getdis(t, j) <= 1000.0) {
44                 dis[j] = getdis(t, j);
45             }
46         }
47     }
48     if(cnt != n) printf("oh!
");
49     else printf("%.1lf
", sum*100.0);
50 }
51 
52 int main() {
53     int T;
54     scanf("%d", &T);
55     while(T--) {
56         scanf("%d", &n);
57         for(int i = 0; i != n; ++i) {
58             scanf("%d%d", &p[i].x, &p[i].y);
59         }
60         prim();
61     }
62     return 0;
63 }
View Code
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/pupil-xj/p/11620318.html