最小生成树模板

题目描述

给出一个无向图，求出最小生成树。如果该图不连通，则输出 'orz'。

输入格式

第一行包含两个整数 $N,M$，表示该图共有 $N$ 个结点和 $M$ 条无向边。

接下来 $M$ 行每行包含三个整数 $X_i,Y_i,Z_i$，表示有一条长度为 $Z_i$ 的无向边连接结点 $X_i,Y_i$。

输出格式

如果该图连通，则输出一个整数表示最小生成树的各边的长度之和。如果该图不连通则输出 'orz'。

样例 #1

样例输入 #1

4 5
1 2 2
1 3 2
1 4 3
2 3 4
3 4 3

样例输出 #1

7

提示

数据规模：

对于 $20%$ 的数据，$N\le 5$，$M\le 20$。

对于 $40%$ 的数据，$N\le 50$，$M\le 2500$。

对于 $70%$ 的数据，$N\le 500$，$M\le 10^4$。

对于 $100%$ 的数据：$1\le N\le 5000$，$1\le M\le 2\times 10^5$，$1\le Z_i \le 10^4$。

样例解释：

所以最小生成树的总边权为 $2+2+3=7$。

C++ 实现

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Edge {
    int u, v, w;
};

int find(vector<int>& parent, int x) {
    if (parent[x] == x) {
        return x;
    }
    return parent[x] = find(parent, parent[x]);
}

void unite(vector<int>& parent, vector<int>& rank, int x, int y) {
    int rootX = find(parent, x);
    int rootY = find(parent, y);
    if (rootX != rootY) {
        if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else {
            parent[rootY] = rootX;
            if (rank[rootX] == rank[rootY]) {
                rank[rootX]++;
            }
        }
    }
}

bool cmp(const Edge& e1, const Edge& e2) {
    return e1.w < e2.w;
}

int main() {
    int N, M;
    cin >> N >> M;
    vector<Edge> edges(M);
    for (int i = 0; i < M; i++) {
        cin >> edges[i].u >> edges[i].v >> edges[i].w;
    }

    // 按照边权从小到大进行排序
    sort(edges.begin(), edges.end(), cmp);

    vector<int> parent(N + 1); // 存储每个结点的父结点
    vector<int> rank(N + 1); // 存储每个结点的秩

    // 初始化父结点和秩
    for (int i = 1; i <= N; i++) {
        parent[i] = i;
        rank[i] = 0;
    }

    int cnt = 0; // 记录生成树的边数
    int ans = 0; // 记录生成树的总边权
    for (int i = 0; i < M; i++) {
        int u = edges[i].u;
        int v = edges[i].v;
        int w = edges[i].w;
        if (find(parent, u) != find(parent, v)) {
            unite(parent, rank, u, v);
            cnt++;
            ans += w;
        }
    }

    if (cnt == N - 1) {
        cout << ans << endl;
    } else {
        cout << "orz" << endl;
    }

    return 0;
}

代码解析

1. 数据结构: 使用 Edge 结构体存储每条边的信息，包含起点 u，终点 v 和边权 w。

2. 并查集: 使用 parent 和 rank 数组实现并查集，用于判断两个结点是否在同一连通块中。

3. 排序: 按照边权从小到大排序所有边，使用 sort 函数实现。

4. Kruskal 算法: 遍历排序后的边，如果当前边的两个端点不在同一个连通块中，则将这条边加入生成树中，并使用 unite 函数将两个连通块合并。

5. 判断连通性: 如果生成树的边数等于结点数减 1，则该图连通，否则不连通。

总结

本文提供了一个最小生成树模板，并使用 C++ 语言实现 Kruskal 算法，代码简洁易懂，并包含详细的注释。希望这篇文章能帮助你理解最小生成树的概念和实现细节，并能够应用到实际问题中。