C++ 编程题解：最小生成树算法求翻新道路最小长度

题目描述：

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

输入描述：

第一行有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}。

思路：

最小生成树（Kruskal 算法）

由于要构成一棵树，所以最后的答案一定是一棵生成树。而最小生成树算法中，Kruskal 算法是比较常用的，因此我们可以使用 Kruskal 算法求出最小生成树，即为所求的翻新道路的最小长度。

具体实现：

将所有边按照权值从小到大排序
依次遍历每条边，如果这条边的两个端点不在同一棵树中，则将它们合并，并将这条边加入生成树中
当生成树中的边数等于 n-1 时，即为一棵生成树，停止遍历并输出生成树中所有边的权值之和

代码实现：

#include <iostream>
#include <algorithm>
#include <vector>
#define MAXN 30005
using namespace std;

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

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

int fa[MAXN];

int find(int x) {
    if (fa[x] == x) return x;
    return fa[x] = find(fa[x]);
}

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);
    for (int i = 1; i <= n; i++) fa[i] = i;
    int cnt = 0, ans = 0;
    for (int i = 0; i < m; i++) {
        int u = find(edges[i].u), v = find(edges[i].v);
        if (u != v) {
            fa[u] = v;
            ans += edges[i].w;
            cnt++;
            if (cnt == n - 1) break;
        }
    }
    cout << ans << endl;
    return 0;
}

说明：

代码中使用了并查集数据结构来判断两个结点是否在同一棵树中。
由于需要排序，因此使用 vector 存储边信息，并在使用前对其进行排序。
遍历边时，如果两个端点不在同一棵树中，则将它们合并，并将这条边加入生成树中。
当生成树中的边数等于 n-1 时，即为一棵生成树，停止遍历并输出生成树中所有边的权值之和。