题解 | 还是畅通工程 kruskal算法、贪心算法、并查集

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;

// 全局数组
int father[1010];

// 结构体 边
struct Edge {
    int u;
    int v;
    int weight;  // 带权图
    // 构造函数的特点 类里面 没有返回值 名字和类名相同
    Edge(int _u, int _v, int _weight) {
        u = _u;
        v = _v;
        weight = _weight;
    }
};

// 初始化
void InitDisjoinSet(int n) {
    for (int i = 0; i < n; i++) {
        father[i] = i;
    }
}

// 查找指定元素的根节点
int FindDisjoinSet(int u) {
    if (u == father[u]) {
        return u;
    } else {
        father[u] = FindDisjoinSet(father[u]);
        return father[u];
    }
}

// 合并
void UnionDisjoinSet(int u, int v) {
    int uroot = FindDisjoinSet(u);
    int vroot = FindDisjoinSet(v);
    father[vroot] = uroot;
}

// 权值排序 比较函数
bool compare(Edge lhs, Edge rhs) {
    // 权值 从小到大 升序
    return lhs.weight < rhs.weight;
}

int main() {
    int n;
    while (scanf("%d", &n) != EOF) {
        if (n == 0) {
            break;
        }
        vector<Edge> edgeVec;
        InitDisjoinSet(n + 1);   // 只使用 1 -> n
        for (int i = 0; i < n * (n - 1) / 2; i++) {
            int u, v, weight;
            scanf("%d%d%d", &u, &v, &weight);
            // Edge e;  // 可以用类的构造函数简化
            // e.u = u;
            // e.v = v;
            // e.weight = weight;
            Edge e(u, v, weight);
            edgeVec.push_back(e);
        }
        //  kruskal
        // 1.权值排序
        sort(edgeVec.begin(), edgeVec.end(), compare);

        // 2.遍历edgeVec加入子图
        int totalWeight = 0;  // 树的总权重
        int curEdgeNum = 0;  // 边数
        vector<Edge>::iterator it;
        for (it = edgeVec.begin(); it != edgeVec.end(); it++) {
            // 不连通才加入
            if (FindDisjoinSet(it->u) != FindDisjoinSet(it->v)) {
                UnionDisjoinSet(it->u, it->v);  // u 到 v 之间连一条边，保证联通
                curEdgeNum++;
                totalWeight += it->weight;
            }
            if (curEdgeNum == n - 1) {  // 3. 边数 = 顶点数 - 1
                break;
            }
        }

        printf("%d\n", totalWeight);
    }
    return 0;
}