18448 最小生成树

### 思路
使用Kruskal算法求解图的最小生成树。Kruskal算法通过对所有边按权值排序，然后逐步选择最小权值的边，确保不会形成环，直到构建出最小生成树。

### 伪代码
1. 读取输入的结点数`n`和边数`m`。
2. 读取每条边的信息，存储在边列表中。
3. 对边列表按权值进行排序。
4. 初始化并查集。
5. 遍历排序后的边列表，逐步选择边并加入最小生成树，确保不会形成环。
6. 输出最小生成树的边权和。

### C++代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Edge {
    int u, v;
    long long w;
    bool operator<(const Edge& other) const {
        return w < other.w;
    }
};

vector<int> parent, rankVec;

int find(int u) {
    if (parent[u] != u) {
        parent[u] = find(parent[u]);
    }
    return parent[u];
}

void unionSets(int u, int v) {
    int rootU = find(u);
    int rootV = find(v);
    if (rootU != rootV) {
        if (rankVec[rootU] > rankVec[rootV]) {
            parent[rootV] = rootU;
        } else if (rankVec[rootU] < rankVec[rootV]) {
            parent[rootU] = rootV;
        } else {
            parent[rootV] = rootU;
            rankVec[rootU]++;
        }
    }
}

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());

    parent.resize(n + 1);
    rankVec.resize(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        parent[i] = i;
    }

    long long mstWeight = 0;
    for (const auto& edge : edges) {
        if (find(edge.u) != find(edge.v)) {
            unionSets(edge.u, edge.v);
            mstWeight += edge.w;
        }
    }

    cout << mstWeight << endl;
    return 0;
}

### 总结
该代码使用Kruskal算法求解图的最小生成树。通过对边按权值排序，使用并查集管理连通性，逐步选择最小权值的边，确保不会形成环，最终输出最小生成树的边权和。

原文地址：https://blog.csdn.net/huang1xiao1sheng/article/details/142731962

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！