洛谷 P1111 修复公路（最小生成树）

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 
 5 using namespace std;
 6 
 7 int f[10005], ans;
 8 int num;
 9 
10 struct node{
11     int x, y, l;
12 } a[100005];
13 
14 inline int cmp(node i, node j){
15     return i.l < j.l;
16 }
17 
18 inline int find(int x){
19     if(f[x] != x)
20         f[x] = find(f[x]);
21     return f[x];
22 }
23 
24 int main(){
25     int n, m;
26     scanf("%d%d", &n, &m);
27     for(int i = 1; i <= n; i++)
28         f[i] = i;
29     for(int i = 1; i <= m; i++){
30         scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].l);
31     }
32     sort(a+1, a+m+1, cmp);
33     for(int i = 1; i <= m; i++){
34         int r1 = find(a[i].x);
35         int r2 = find(a[i].y);
36         if(r1 != r2){
37             f[r1] = r2;
38             num++;//道路数量 
39             ans = max(ans, a[i].l);//时间 
40         }
41     }
42     if(num >= n - 1) printf("%d", ans);
43     else printf("-1");
44     return 0;
45 }