最后一个测试点WA,帮忙看一下判断orz的部分
查看原帖
最后一个测试点WA,帮忙看一下判断orz的部分
816204
Light_LE楼主2024/10/19 15:43

rt

#include <bits/stdc++.h>
#define maxn 200005
using namespace std;
struct Edge {
	int u, v, w;
}edge[maxn];
int n, m, fa[5003], cnt/*判断图是否连通*/, ans;
bool cmp(Edge x, Edge y) {
	return x.w < y.w;
}
int get(int x) {
	if (x == fa[x]) {
		return x;
	}
	return fa[x] = get(fa[x]);
}
bool kruskal() {
	for (int i = 1; i <= n; i++) {
		fa[i] = i;
	}
	sort(edge + 1, edge + m + 1, cmp);
	for (int i = 1; i <= m; i++) {
		int x = get(edge[i].u), y = get(edge[i].v);
		if (x == y) {
			continue;
		}
		fa[x] = y;
		ans += edge[i].w;
		
		if (cnt++ == n - 1) {// 利用生成树的定义判断图是否连通
			return 0;
		}
	}
	return 1;// 正确得到结果
}
int main() {
	//freopen("in.txt", "r", stdin);
	ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);
	
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		edge[i].u = u, edge[i].v = v, edge[i].w = w;
	}
	
	if (kruskal()) {
		cout << ans;
	}
	else {
		cout << "orz";
	}
	return 0;
}
2024/10/19 15:43
加载中...