第36698题 组合题
完善程序(第一题):Kruskal 最小生成树

(最小生成树)给定一个含 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;
}
{{ option.label }}
子题{{ index + 1 }} {{ child.type_label }}
{{ option.label }}
✓ 正确 ◐ 部分正确 ✗ 错误
程序运行统计
暂无判题统计
知识点:
提交{{ questionInfo.stats ? questionInfo.stats.submit_count : 0 }}次 正确率{{ statsAccuracy }}%
答案解析