市场营销专业网站,怎么做百度推广平台,百度商标查询,wordpress分类列表文章目录 题目描述输入格式输出格式样例样例输入样例输出 完整代码 题目描述
Bessie 计划调查 N N N#xff08; 2 ≤ N ≤ 2 000 2 \leq N \leq 2\,000 2≤N≤2000#xff09;个农场的干草情况#xff0c;它从 1 1 1 号农场出发。农场之间总共有 M M M#xff08; 1 ≤… 文章目录 题目描述输入格式输出格式样例样例输入样例输出 完整代码 题目描述
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;
}
