RT,初始化灵异事件,kruscal
查看原帖
RT,初始化灵异事件,kruscal
537719
hanss6楼主2024/7/11 14:12

代码第47行并查集数组初始化,初始化到大N这个常量,小n也会变成大N的值,换成小n或者是小n + 任何常数都正常AC,我在第30行有输出小n的代码,求解答

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+5;

struct edge{
	int from, to, val;
} e[N];

bool cmp(edge a, edge b) {
	return a.val < b.val;
}
int fa[N];
int find(int x) {
	if(fa[x] == x) return x;
	return fa[x] = find(fa[x]);
}
int n, m, k;
int tot = 0;
int cnt = 0, dis = 0;
bool kurscal() {
	sort(e + 1, e + 1 + tot, cmp);
	for(int i = 1; i <= tot; i++) {
		int x = find(e[i].from), y = find(e[i].to);
		if(x != y) {
			fa[y] = x;
			cnt++;
			dis += e[i].val;
		}
		cout << n << ' ' << cnt << endl;
		if(n - cnt == k) return 1;
	}
	return 0;
}


int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n >> m >> k;
	for(int i = 1; i <= m; i++) {
		int x, y, l;
		cin >> x >> y >> l;
		e[++tot].from = x;
		e[tot].to = y;
		e[tot].val = l;
	}
	for(int i = 1; i <= N; i++) fa[i] = i;
	if(kurscal()) cout << dis;
	else cout << "No Answer";
	return 0;
}
2024/7/11 14:12
加载中...