洛谷 P1111 修复公路

题目传送门

解题思路:

本题说让任意两个点都可以互相到达,其实就是这n个点连接成一个联通块,一开始有n个联通块,每当有两个原本不在同一联通块的点连在一起,连通块数量减一,直到只剩一块.

AC代码:

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm> 
 4 
 5 using namespace std;
 6 
 7 int n,m,fa[1001],tot = 1;
 8 bool p[1001];
 9 struct kkk {
10     int from,to,t;
11 }e[100001];
12 
13 inline int find_father(int x) {
14     if(fa[x] == x) return x;
15     return fa[x] = find_father(fa[x]);
16 } 
17 
18 bool cmp(kkk a,kkk b) {
19     return a.t < b.t;
20 }
21 
22 int main()
23 {
24     scanf("%d%d",&n,&m);
25     for(int i = 1;i <= n; i++) fa[i] = i;
26     for(int i = 1;i <= m; i++) 
27         scanf("%d%d%d",&e[i].from,&e[i].to,&e[i].t);
28     sort(e+1,e+1+m,cmp);
29     for(int i = 1;i <= m; i++) {
30         int x = find_father(e[i].from);
31         int y = find_father(e[i].to);
32         if(x != y) {
33             tot++;
34             fa[x] = y;
35         }
36         if(tot == n) {
37             printf("%d",e[i].t);
38             return 0;
39         }
40     }
41     printf("-1");
42     return 0;
43 }