10分求调(MLE)
查看原帖
10分求调(MLE)
1331158
yuer111楼主2024/12/15 16:55
#include<bits/stdc++.h>
using namespace std;
int fa[10005], n, m;
int cnt, MST;
struct node {
	int x, y, z;
} e[2005];
int find(int x) {
	if (x != fa[x]) fa[x] = find(fa[x]);
	else return fa[x];
}
void solve() {
	for (int i = 1; i <= m; i++) {
		int rx = find(e[i].x);
		int ry = find(e[i].y);
		if (rx == ry) continue;
		fa[rx] = ry;
		MST = e[i].z;
		cnt++;
		if (cnt == n - 1) break;
	}
}
bool cmp(node a, node b) {
	return a.z < b.z;
}
int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		fa[i] = i;
	for (int i = 1; i <= m; i++)
		cin >> e[i].x >> e[i].y >> e[i].z;
	sort(e + 1, e + 1 + m, cmp);
	solve();
	cout << MST;
	return 0;
}
2024/12/15 16:55
加载中...