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}。

输出描述：

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

思路：

Kruskal 算法求最小生成树

首先需要将边按照权值从小到大排序，然后从小到大依次加入边，如果加入的边不会形成环，则加入该边，否则舍弃该边。

需要注意的是，题目中要求所有翻新的路段必须构成一棵树，因此需要判断当前加入的边是否会使得已有的边集合不再是一棵树。

具体实现时，可以使用并查集来维护边集合的连通性。

时间复杂度为 O(mlogm)，m 为边数。

参考代码：

#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 par[30005];

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

void merge(int x, int y) {
    par[find(x)] = find(y);
}

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