P1547 [USACO05MAR] Out of Hay S 题解

题解"/>

P1547 [USACO05MAR] Out of Hay S 题解

文章目录

• • 题目描述
  • 输入格式
  • 输出格式
  • 样例
  • • 样例输入
    • 样例输出
  • 完整代码

题目描述

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

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

输入格式

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

接下来 M M M 行，每行三个用空格隔开的整数 A i , B i , L i A_i,B_i,L_i Ai​,Bi​,Li​，表示 A i , B i A_i,B_i Ai​,Bi​ 之间有一条道路，长度为 L i L_i Li​。

输出格式

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

样例

样例输入

3 3
1 2 23
2 3 1000
1 3 43

样例输出

43

完整代码

#include <bits/stdc++.h>
using namespace std;
struct node {int to, nxt, w;
} e[1000002];
int f[200002];
int find(int x) {if (x == f[x])return x;elsereturn 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;
}