题解

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

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

const int INF = 1e9;

int find(int x, vector<int>& parent) {
    if (parent[x] == x)
        return x;
    return parent[x] = find(parent[x], parent);
}

void unite(int x, int y, vector<int>& parent, vector<int>& rank) {
    x = find(x, parent);
    y = find(y, parent);
    if (rank[x] < rank[y])
        parent[x] = y;
    else {
        parent[y] = x;
        if (rank[x] == rank[y])
            rank[x]++;
    }
}

int minimumCost(vector<Edge>& edges, int N) {
    vector<int> parent(N);
    vector<int> rank(N, 0);
    
    for (int i = 0; i < N; i++) {
        parent[i] = i;
    }
    
    sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) {
        return a.cost < b.cost;
    });
    
    int minCost = 0;
    int numComponents = N;
    
    for (const auto& edge : edges) {
        int u = edge.u;
        int v = edge.v;
        int cost = edge.cost;
        
        if (find(u, parent) != find(v, parent)) {
            unite(u, v, parent, rank);
            minCost += cost;
            numComponents--;
        }
    }
    
    return minCost;
}

int main() {
    int T;
    cin >> T;
    
    while (T--) {
        int N, E;
        cin >> N >> E;
        
        vector<Edge> edges(E);
        for (int i = 0; i < E; i++) {
            cin >> edges[i].u >> edges[i].v >> edges[i].cost;
        }
        
        int minCost = minimumCost(edges, N);
        cout << minCost << endl;
    }
    
    return 0;
}