UVa11631 - Dark Roads(Kruskal)

題目大意

Byteland 這座城市想要節省電費，因此想要在晚上把路燈給關掉，每一公尺就需要花一塊錢，但是要是整座城市都沒有路燈就太可怕了！於是 Byteland 折衷，她希望可以有一個明亮的路徑通往到每一個道路上，因此他想問說，如果只有一條明亮的路徑並且可以通往到每個道路上，那我將其他燈都關掉可以省下多少成本

題目連結

重點觀念

• Kruskal by 大衞的筆記

分析

• 只要看懂題目大意後就會知道，其實是一個最小生成樹，只要讓每一條路可以抵達其他路即可。

參考連結

UVa 11631 - Dark Roads

題目程式碼

會在下面放一些簡單註解，供大家學習時參考。

關於 kruskal 詳解請參考 Kruskal by 大衞的筆記

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define MAXN 200020
#define int long long
using namespace std;
int n, m;
int a, b, c;
int p[MAXN];

struct edge{
    int u, v, c; 
    edge(){
        u = 0, v = 0, c = 0;
    }
    edge(int _u, int _v, int _c){
        u = _u, v = _v, c = _c;
    }
    bool operator < (const edge& other) const{
        return c < other.c;
    }
};
vector<edge> node;
vector<edge> remain; //放入沒有被用入 edge，記錄省下成本

int find_root(int x){
    //cout << "find_root " << x << "\n";
    if(p[x] != x) return p[x] = find_root(p[x]);
    return x;
}

int32_t main()
{
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif // LOCAL

    while(cin >> n >> m && (n+m) != 0){
        node.clear();
        remain.clear();
        for(int i = 0; i < n; i++) p[i] = i;

        for(int i = 0; i < m; i++){
            cin >> a >> b >> c;
            node.push_back({a,b,c});
        }
        sort(node.begin(), node.end());

        for(edge it: node){
            //cout << it.u << " " << it.v << " " << it.c << "\n";
            //cout << p[3] << " " << p[4] << "\n";
            int pu = find_root(it.u);
            int pv = find_root(it.v);
            if(pu != pv) p[pv] = pu;
            else remain.push_back(it); //紀錄沒被用到的邊

        }

        int ans = 0;
        for(edge it: remain) ans += it.c; //計算總和
        cout << ans << "\n";


    }
    return 0;
}