P1111 修复公路

 1 #include<iostream>
 2 #include<algorithm>
 3 using namespace std;
 4
 5 int fa[1010];
 6 int n, m;
 7
 8 int find(int x)
 9 {
10     if (fa[x] == x) return x;
11     fa[x] = find(fa[x]);
12     return fa[x];
13 }
14
15 void merge(int a,int b)
16 {
17     fa[find(a)] = find(b);
18 }
19
20 struct Edge
21 {
22     int u, v, t;
23 }e[100010];
24
25 bool cmp(Edge a, Edge b)
26 {
27     return a.t < b.t;
28 }
29
30 int main()
31 {
32     cin >> n >> m;
33     for (int i = 1; i <= m; i++)
34     {
35         cin >> e[i].u >> e[i].v >> e[i].t;
36     }
37     sort(e + 1, e + m + 1, cmp);
38     int cnt = 1;
39     int t = -1;
40     for (int i = 1; i <= n; i++)
41     {
42         fa[i] = i;
43     }
44     for (int i = 1; i <= m; i++)
45     {
46         if (find(e[i].u) != find(e[i].v))
47         {
48             merge(e[i].u, e[i].v);
49             cnt++;
50             if (cnt == n)
51             {
52                 t = e[i].t;
53                 break;
54             }
55         }
56     }
57     if (cnt == n) cout << t;
58     else cout << -1;
59 }

View Code