79pts求调 包关注qwq
查看原帖
79pts求调 包关注qwq
1491323
Neptunes楼主2025/1/19 19:24

HELP! Kruskal 算法 包关注包关注包关注qwq

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5+5;
int n, m;
int ans;
int u[N], v[N], w[N], b[N];
int f[N];
int cmp(int i, int j)
{
	return w[i] < w[j];
}
int find(int x)
{
	return f[x] == x ? x : f[x] = find(f[x]);
}
signed main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++)f[i] = i;
	for (int i = 1; i <= m; i++)cin >> u[i] >> v[i] >> w[i], b[i] = i;
	sort(b + 1, b + m + 1, cmp);
	for (int i = 1; i <= m; i++)
	{
		int e = b[i];
		int x = find(u[e]), y = find(v[e]);
		if (x != y)
		{
			ans += w[e];
			f[x] = y;
		}
	}
	for (int i = 1; i <= n; i++)if (find(i)!= find(1))
	{
		cout << "orz";
		return 0;
	}
	cout << ans;
}

2025/1/19 19:24
加载中...