【題解】ZeroJudge d909: 公路局長好煩惱!?

【題目敘述】https://zerojudge.tw/ShowProblem?problemid=d909
【解題想法】最小生成樹 (MST)

  • n個節點的樹,有n-1條邊。建構一棵權重和最小的樹。(用最少的錢把Waku的每個城鎮都連接起來。)
  • 每條公路依建造成本排序。
  • 利用並查集的Union Find algorithm合併這些公路。
#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;
}

分享本文 Share with friends