50PTS求助
查看原帖
50PTS求助
727587
Merlin_Meow楼主2023/2/24 18:39
#include<bits/stdc++.h>
using namespace std;
inline int read() {
	int x = 0, f = 1;
	char ch = getchar();
	while (ch < '0' || ch > '9') {
		if (ch == '-') f = -1;
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9') {
		x = (x << 1) + (x << 3) + (ch ^ 48);
		ch = getchar();
	}
	return x * f;
}
struct edge {
	int s, t, w;
} e[10001];
bool cmp(edge a, edge b) {
	return a.w < b.w;
}
int fa[2001];
int find(int x) {
	if (fa[x] == x) return x;
	return fa[x] = find(fa[x]);
}
void join(int c1, int c2) {
	int f1 = find(c1), f2 = find(c2);
	if (f1 != f2) fa[f1] = f2;
}
int main() {
	int n = read(), m = read();
	for (int i = 1; i <= m; i++) {
		e[i].s = read();
		e[i].t = read();
		e[i].w = read();
	}
	for (int i = 1; i <= n; i++) fa[i] = i;
	sort(e + 1, e + m + 1, cmp);
	int ans = 0, maxn = -1;
	for (int i = 1; i <= m; i++) {
		join(e[i].s, e[i].t);
		ans++;
		if (e[i].w > maxn)
			maxn = e[i].w;
		if (ans == n - 1) {
			cout << maxn;
			return 0;
		}
	}
	return 0;
}
2023/2/24 18:39
加载中...