1 #include <iostream>
2 #include <cstdio>
3 #include <algorithm>
4 #include <cmath>
5 using namespace std;
6
7 const int maxn =
500;
8
9 int n, m;
10 int x[maxn], y[maxn], f[maxn];
11 int ans =
0;
12
13 struct node {
14 int x, y;
15 int val;
16 }dis[
50100];
17
18 bool cmp(node a, node b) {
19 return a.val <
b.val;
20 }
21
22 int find(
int x) {
23 int r =
x;
24 while(r != f[r]) r =
f[r];
25 int i =
x, j;
26 while(f[i] !=
r) {
27 j =
f[i];
28 f[i] =
r;
29 i =
j;
30 }
31 return r;
32 }
33
34 void merge(
int x,
int y) {
35 x =
find(x);
36 y =
find(y);
37 if(x != y) f[y] =
x;
38 }
39
40 int main() {
41 cin >> n >>
m;
42 for(
int i =
1; i <= m; i++
) {
43 cin >> dis[i].x >> dis[i].y >>
dis[i].val;
44 }
45 for(
int i =
1; i <= n; i++) f[i] =
i;
46
47 sort(dis +
1, dis + m +
1, cmp);
48 int tmp =
0, maxn =
0;
49 for(
int i =
1; i <= m; i++
) {
50 if(find(dis[i].x) !=
find(dis[i].y)) {
51 merge(dis[i].x, dis[i].y);
52 tmp++
;
53 maxn =
max(maxn, dis[i].val);
54 }
55 if(tmp == n -
1)
break;
56 }
57
58 cout << tmp <<
' ' <<
maxn;
59 }
转载于:https://www.cnblogs.com/MekakuCityActor/p/8989498.html
