最小生成树笔记

ykj12 2023-11-04 19:40:36 2023-11-04 19:40:45 2

#6673. 【模板】最小生成树

#include<bits/stdc++.h>

using namespace std;

const int N = 2e5 + 10;
struct edge {
	int u, v, w;
} a[N], mst[N];
int n, m;
int ans = 0, k;  
int p[5010];

int find (int x) {
	if (p[x] == x) {
		return x;
	}
	return p[x] = find (p[x]);
}
void Union (int a, int b) {
	int fa = find (a), fb = find (b);
	if (fa != fb) p[fa] = fb;
}
bool cmp (edge x, edge y) {
	return x.w < y.w;
}


int main(){
	scanf ("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) {
		p[i] = i;
	}
	for (int i = 1; i <= m; i++) {
		int u, v, w;
		scanf ("%d%d%d", &u, &v, &w);
		a[i] = {u, v, w};
	}
	sort (a + 1, a + 1 + m, cmp);
	for (int i = 1; i <= m; i++) {
		if (find(a[i].u) != find(a[i].v)) {
			Union (a[i].u, a[i].v);
			mst [++k] = a[i];
			ans += a[i].w;
			if (k == n - 1) break;
		}
	}
	if (k != n - 1) cout << "orz" << endl;
	else cout << ans << endl;
	//克鲁斯卡尔算法 
	return 0;
}

{{ vote && vote.total.up }}

共 1 条回复

Kinghero King of the summit

%%%%%%%%%%%%