Kruskal 最小生成树

CSP-J · 编程模板 · 片段 · cpp · 难度 3/5 · 共 917 字

边按权排序贪心选，并查集判是否成环

图论
最小生成树

前置内容

并查集

正文

// Kruskal：最小生成树
// 边按权排序，贪心选边
// 用并查集判是否成环
// 选满 n-1 条边即完成
#include <cstdio>
#include <algorithm>
using namespace std;
struct Edge { int u, v, w; } e[200005];
int fa[10005], n, m, ans = 0, cnt = 0;
// 按权升序比较
bool cmp(Edge a, Edge b) {
    // 按权升序比较
    return a.w < b.w;
}
// 找根（路径压缩）
int find(int x) {
    if (fa[x] != x) fa[x] = find(fa[x]);
    return fa[x];
}
int main() {
    scanf("%d%d", &n, &m);
    // 初始化并查集
    for (int i = 1; i <= n; i++) fa[i] = i;
    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 <= m; i++) {
        int ru = find(e[i].u),
            rv = find(e[i].v);
        // 两端已连通则跳过
        if (ru == rv) continue;
        fa[ru] = rv;
        // 累加边权
        ans += e[i].w;
        // 边数够了即停止
        if (++cnt == n - 1) break;
    }
    printf("%d", ans);
    return 0;
}

Kruskal 最小生成树

前置内容

正文

CSP-J · 编程模板的其它内容