洛谷P1111修复公路

思路：并查集

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 #include<math.h>
 5 #include<vector>
 6 #include<set>
 7 using namespace std;
 8 
 9 int f[1005] = { 0 };
10 
11 int find(int x) { return f[x] == x ? x : f[x] = find(f[x]); }
12 void merge(int i, int j) { f[find(i)] = find(j); }
13 
14 bool judge(int n) {         //判断所有村庄是否连通
15     int x = find(0);
16     for (int i = 0; i < n; i++) {
17         if (find(f[i]) != x) return false;
18     }
19     return true;
20 }
21 struct road {
22     int a, b, c;
23 }x[100005];
24 struct cmp {        //自定义multiset容器排序规则(升序)
25     bool operator()(const road& a, const road& b) const{
26         return a.c < b.c || a.c == b.c;
27     }
28 };
29 int main() {
30     int n, m;
31     bool fx = false;
32     multiset<road,cmp>h;
33     scanf("%d %d", &n, &m);
34     for (int i = 0; i < n; i++) f[i] = i;   //初始化  
35     for (int i = 0; i < m; i++) {
36         scanf("%d %d %d", &x[i].a, &x[i].b,&x[i].c);
37         h.insert(x[i]);
38     }
39     for (multiset<road>::iterator it = h.begin(); it != h.end(); it++) {
40         //printf("%d %d %d\n",(*it).a, (*it).b, (*it).c);
41         merge((*it).a, (*it).b);
42         if (judge(n)) {
43             printf("%d", (*it).c);
44             fx = true;
45             break;
46         }
47     }
48     if(!fx) printf("-1");
49     return 0;
50 }