【題解】ZeroJudge d909: 公路局長好煩惱！？

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct e{
    int x, y;
    int cost;
};

bool cmp(e x, e y){
    return x.cost < y.cost;
}

int n, m, x, y, c, todo, p[100000];
long long ans;

int find(int a){
    if (p[a] == a) return a;
    else {
        p[a] = find(p[a]);
        return p[a];
    }
}

vector <e> v;

int main() {
    while (cin >> n >> m){
        todo = n-1;//n個節點的樹，有n-1條邊
        ans = 0;
        v.clear();
        for (int i = 0; i < n; i++){
            p[i] = i;
        }
        for (int i = 0; i < m; i++){
            cin >> x >> y >> c;
            v.push_back({x, y, c});
        }
        //針對cost排序，由小排到大
        sort(v.begin(), v.end(), cmp);
        for (e tmp:v){
            //disjoint set, union find algorithm
            x = find(tmp.x);
            y = find(tmp.y);
            if (x == y) continue;
            else {
                p[y] = x;
                todo -= 1;
                ans += tmp.cost;
            }
        }
        if (todo == 0) cout << ans << "\n";
        else cout << "-1\n";
    }
    return 0;
}