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

hb782116 组合题 共 个子题

(最小生成树)给定一个含 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;
}

子题 单选题

①处应填( )

A

fa[x] == x

B

x

C

fa[x] != 0

D

fa[x] == fa[fa[x]]

子题 单选题

②处应填( )

A

0

B

1

C

i

D

n

子题 单选题

③处应填( )

A

ru != rv

B

ru == rv

C

ru == rv + 1

D

ru < rv

子题 单选题

④处应填( )

A

cnt += 2

B

--cnt

C

++cnt

D

cnt = n - 1

子题 单选题

⑤处应填( )

A

cnt == n

B

cnt == n - 1

C

cnt == n - 2

D

cnt > n - 1

正在加载题目数据…
已答 /
子题
该题型需在试卷/作业中作答,单题练习暂不支持
答案解析
讨论
发布
登录后参与讨论 立即登录
发布讨论需先绑定并验证手机号 去绑定手机号
加载中…
我
我
回复 @
回复 @
发送
还没有人讨论,来发表第一条吧