【正经题解】建设电力系统

#include<bits/stdc++.h>
using namespace std;

// 定义边的结构体
struct Edge {
    int u, v, w;  // u和v表示电力线路的起始村庄代号，w表示线路的权重（正常情况下为0，需要重建时为正整数）
    Edge() {}
    Edge(int uu, int vv, int ww) {
        u = uu, v = vv, w = ww;
    }
};

// 边的比较函数，用于排序
bool compareEdges(Edge a, Edge b) {
    return a.w < b.w;
}

const int MAX_VILLAGES = 510;

// 并查集的初始化
void initialize(int fa[]) {
    for (int i = 0; i < MAX_VILLAGES; i++) {
        fa[i] = i;
    }
}

// 获取节点所在集合的代表节点
int find(int x, int fa[]) {
    if (fa[x] == x)
        return x;
    else {
        int root = find(fa[x], fa);
        fa[x] = root;  // 路径压缩
        return root;
    }
}

// 合并两个集合
bool unionSets(int x, int y, int fa[]) {
    int root1 = find(x, fa);
    int root2 = find(y, fa);
    if (root1 == root2) {
        return false;  // x和y已经在同一个集合中
    } else {
        fa[root1] = root2;  // 合并两个集合
        return true;  // 合并成功
    }
}

int main() {
    int t;
    cin >> t;
    for (int case_num = 1; case_num <= t; case_num++) {
        int total_cost = 0;
        int fa[MAX_VILLAGES];
        initialize(fa);

        int n, e;
        cin >> n >> e;
        Edge edges[MAX_VILLAGES * (MAX_VILLAGES - 1) / 2];

        // 读取边信息
        for (int i = 1; i <= e; i++) {
            int u, v, w;
            cin >> u >> v >> w;
            edges[i] = Edge(u, v, w);
        }

        // 将边按权重从小到大排序
        sort(edges + 1, edges + 1 + e, compareEdges);

        // 遍历边，按最小生成树的方式合并节点
        for (int i = 1; i <= e; i++) {
            if (unionSets(edges[i].u, edges[i].v, fa)) {
                total_cost += edges[i].w;
            }
        }

        cout << total_cost << endl;
    }
    return 0;
}