C++ 实现道路翻新最小成本规划：Kruskal 算法求最小生成树

问题描述:

老张在一家工程公司担任规划师。一天，这个工程公司接到了市政府的道路翻新任务，需要在已有的路网上规划一些路段进行翻新，并保证规划中的翻新道路经过了所给路网上所有的结点（一段翻新道路经过其两端的结点），同时所有翻新的路段必须构成一棵树，也就是说不可以存在一段不与其他翻新路段相连的翻新路段。因为翻新成本与道路长度有关，所以需要规划翻新的道路长度和最小，老张想请你帮忙计算这个最小长度和。

输入描述:

第一行有2个正整数 n 和 m，表示所给路网的结点数和道路数。

接下来有 3 行，每一行有 m 个正整数，每行分别对应 ui、vi、wi。

相同位置的一组<ui, vi, wi> 表示结点 ui 和 vi 之间有一条长度为 wi 的道路。

输入中的数字，两两间均有空格隔开

1 ≤ ui, vi ≤ n，0 ≤ wi ≤ 1000，1 ≤ m ≤min{30000, n2}。

输出描述:

输出 1 行，只包括 1 个整数，表示题目所求的最小长度和。

思路：Kruskal 算法求最小生成树

将边按权值从小到大排序
依次加入边，如果加入的边使得图中出现环，则不加入
直到加入的边数为 n-1（n 为节点数），此时的边权和即为最小生成树的权值和

注意：题目要求最小生成树必须包含所有节点，因此在判断是否出现环的时候需要判断是否已经包含所有节点。

时间复杂度: O(mlogm)，其中 m 为边数。排序需要 O(mlogm) 的时间，加入边的过程中每条边最多被判断一次是否形成环，因此总时间复杂度为 O(mlogm)。

代码实现:

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

using namespace std;

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

bool cmp(const Edge& a, const Edge& b) {
    return a.w < b.w;
}

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

int kruskal(vector<Edge>& edges, int n) {
    vector<int> fa(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        fa[i] = i;
    }

    sort(edges.begin(), edges.end(), cmp);

    int cnt = 0;
    int sum = 0;
    for (int i = 0; i < edges.size(); ++i) {
        int u = edges[i].u;
        int v = edges[i].v;
        int w = edges[i].w;
        int fu = find(fa, u);
        int fv = find(fa, v);
        if (fu != fv) {
            fa[fu] = fv;
            sum += w;
            cnt++;
        }
        if (cnt == n - 1) {
            break;
        }
    }
    return sum;
}

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;
    }
    cout << kruskal(edges, n) << endl;
    return 0;
}