P1547 [USACO05MAR] Out of Hay S 题解

题目描述

Bessie 计划调查 $N$（$2\le N\le 2000$）个农场的干草情况，它从 $1$ 号农场出发。农场之间总共有 $M$（$1\le M\le 10^4$）条双向道路，所有道路的总长度不超过 $10^9$。有些农场之间存在着多条道路，所有的农场之间都是连通的。

Bessie 希望计算出该图中最小生成树中的最长边的长度。

输入格式

第一行两个整数 $N,M$。

接下来 $M$ 行，每行三个用空格隔开的整数 $A_i,B_i,L_i$，表示 $A_i,B_i$ 之间有一条道路，长度为 $L_i$。

输出格式

一个整数，表示最小生成树中的最长边的长度。

样例

样例输入

3 3
1 2 23
2 3 1000
1 3 43
1
2
3
4

样例输出

43
1

完整代码

#include 
using namespace std;
struct node {
    int to, nxt, w;
} e[1000002];
int f[200002];
int find(int x) {
    if (x == f[x])
        return x;
    else
        return f[x] = find(f[x]);
}
bool cmp(node x, node y) { return x.w < y.w; }
int main() {
    int n, m, cnt = -1;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) scanf("%d%d%d", &e[i].to, &e[i].nxt, &e[i].w);
    sort(e + 1, e + m + 1, cmp);
    for (int i = 1; i <= n; i++) f[i] = i;
    for (int i = 1; i <= m; i++) {
        int k = find(e[i].to), l = find(e[i].nxt);
        if (k != l)
            f[k] = l, cnt = max(cnt, e[i].w);
    }
    printf("%d", cnt);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27