最小生成树模板题

用 Kruskal 即可

不懂戳这里

#include <bits/stdc++.h>
using namespace std;
const int N = 3e5;
int fa[N];
int n, m;

int find(int x) {
	return fa[x] == x ? x : fa[x] = find(fa[x]);
}
int ans, cnt;

struct Edge {
	int v, u, w;
	bool operator<(const Edge &rhs)const {
		return w < rhs.w;
	}
} e[N];

void Kruskal() {
	for (int i = 1; i <= n; i++)
		fa[i] = i;
	sort(e + 1, e + 1 + m);
	for (int i = 1; i <= m; i++) {
		int u = e[i].u, w = e[i].w, v = e[i].v;
		if (find(u) != find(v)) {
			ans += w;
			fa[find(u)] = find(v);
			if (++cnt == n - 1)
				break;
		}
	}
		cout << ans;
}

int main() {
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		cin >> e[i].u >> e[i].v >> e[i].w;
	}
	Kruskal();
	return 0;
}