範例程式碼 uva1234

//uva1234
#include <iostream>
#include <vector>
#include <queue>
#include <tuple>

using namespace std;

#define INF 0x3f3f3f3f

vector<int> UF;

int FIND(int x){
    if (UF[x] == x) return x;
    return UF[x] = FIND(UF[x]);
}
void UNION(int x, int y){
    if (FIND(x)!=FIND(y))
        UF[FIND(x)] = FIND(y);
}

int main() {
    int kase;
    cin>>kase;
    while(kase--) {
        int n, m, sum=0;
        cin>>n>>m;
        UF.resize(n);
        for(int i=0;i<n;i++)UF[i] = i;
        vector<pair<int, int>> edges;
        priority_queue<pair<int, int>> q;
        for(int i=0;i<m;i++){
            int b, e, w;
            cin>>b>>e>>w;
            sum += w;
            edges.push_back({b-1, e-1});
            q.push({w, i});
        }
        while(q.size()){
            int w, idx;
            tie(w, idx) = q.top();
            q.pop();
            if(FIND(edges[idx].first) != FIND(edges[idx].second)){
                sum -= w;
                UNION(edges[idx].first, edges[idx].second);
            }
        }
        cout<<sum<<endl;
    }
    return 0;
}