题解

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

using namespace std;

// 边结构体
struct Edge {
int u, v, weight;
};

// 并查集，用于判断两个节点是否在同一连通块中
class UnionFind {
public:
UnionFind(int n) : parent(n + 1), rank(n + 1, 0) {
for (int i = 1; i <= n; i++) {
parent[i] = i;
}
}

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

void merge(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);
    if (rank[rootX] > rank[rootY]) {
        parent[rootY] = rootX;
    } else {
        parent[rootX] = rootY;
        if (rank[rootX] == rank[rootY]) {
            rank[rootY]++;
        }
    }
}

private:
vector<int> parent;
vector<int> rank;
};

// 最小生成树算法（Kruskal）
int minimumSpanningTree(int n, vector<Edge>& edges) {
// 按边权重升序排序
sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) {
return a.weight < b.weight;
});

UnionFind uf(n); // 初始化并查集
int totalWeight = 0; // 总权重
int edgeCount = 0; // 加入MST的边数

for (const Edge& edge : edges) {
    int u = edge.u;
    int v = edge.v;
    int weight = edge.weight;

    // 若u和v不在同一连通块中，则将边加入MST
    if (uf.find(u) != uf.find(v)) {
        uf.merge(u, v);
        totalWeight += weight;
        edgeCount++;
        if (edgeCount == n - 1) {
            break; // MST已经包含了所有节点，停止添加边
        }
    }
}

return totalWeight;

}

int main() {
int n, m;
cin >> n >> m;

vector<Edge> edges(m);
for (int i = 0; i < m; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    edges[i] = {u, v, w};
}