(最小生成树)给定一个含 n 个点、m 条边的无向带权图(边权为非负整数,可能存在重边与自环)。求其最小生成树的总权值;若图不连通,输出 −1。
以下代码用 Kruskal 算法求解:先按边权从小到大排序,再用并查集依次尝试加入每条边,最后判断是否恰好选出 n − 1 条边。试补全程序。
#include <algorithm>
#include <cstdio>
using namespace std;
const int MAXN = 200005;
struct Edge { int u, v, w; } e[MAXN];
int fa[MAXN];
bool cmp(const Edge &a, const Edge &b) { return a.w < b.w; }
int find(int x) {
if (___①___) return x;
return fa[x] = find(fa[x]);
}
int main() {
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; ++i)
scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w);
sort(e + 1, e + m + 1, cmp);
for (int i = 1; i <= n; ++i) fa[i] = ___②___;
int cnt = 0;
long long ans = 0;
for (int i = 1; i <= m && cnt < n - 1; ++i) {
int u = e[i].u, v = e[i].v;
int ru = find(u), rv = find(v);
if (___③___) continue;
fa[ru] = rv;
ans += e[i].w;
___④___;
}
if (___⑤___) printf("%lld\n", ans);
else printf("-1\n");
return 0;
}