UVa1265 - Tour Belt(Kruskal)

題目大意

Korea 群島可以組成很多種旅遊行程，那如果是兩個島連在一起所產生的好處稱為 SE(協同效應)，再來我們定義協同效應

• 有一張連通圖裡面有 n 個頂點、m 個邊
• SE 必須使用兩頂點組成(也就是邊)，且不可以有重複地點用到
• 再來我們要在一張圖中組成協同效應，其中協同效應必須要選大的，並且要在圖中找出最多的 SE。
• 如果可以有多組以上的協同效應，那麼我們必須確認我們選的邊必須要大於內部的協同效應

簡單來說就是使用 kruskal 找出最大的 SE，並檢查有沒有辦法再跟其他 SE 組成一個更大的 SE。
並將所有 SE 的 size 總合起來輸出。

我題目講的沒有很清楚，這題要去看題目才好理解，不太好解釋。有點出得很難懂..
題目連結

重點觀念

• 超級讚的英文
• Kruskal by 大衞的筆記

分析

• 由於有一種可能性是 SE 與 SE 再組成更大的 SE
• 題目有說明 SE 與 SE 中間不可以有比這兩個 SE 之間更大的 SE，否則應該拿更大的 SE 去跟別的 SE 產生新的 SE。
• 我們要證明第二點，那就先使用 Kruskal 不斷地從最大點 SE 做生成
  • 只要生成樹的內部 SE 沒有比生成樹外部的 SE 小，我們就可以知道這邊會再多一組 SE
  • 因為 SE 會先從最大的開始產生，因此兩個大 SE 如果裡面包著小 SE，那麼那兩個大 SE 還是可以再組成一組 SE
  • 因此只要確認
    • 兩個大 SE 包著小 SE 最大值 大於 兩個大 SE 以外的 SE 最小值 就可以計入答案
    • 因為如果兩個大 SE 以外的 SE 還有更小值的話，那麼應該要讓兩個大 SE 去包她才對。
• 剩下的直接看 code 理解。

參考連結

uva 1265 - Tour Belt by morris
uva 1265 - Tour Belt（生成树） by CDSN

心得

這一次真的寫不太好，但是不太知道要怎麼解釋，非常抱歉，請大家見諒

題目程式碼

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

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

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define MAXN 5020
#define INF 0x3f3f3f
#define int long long
using namespace std;
int t, n, m;
int a, b, c;
int p[MAXN], length[MAXN]; //length 表示以 i 為中心的生成樹，裡面的 sum SE 有多少
vector<pair<int,int> > edges[MAXN];

struct edge{
    int u, v, c; //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;

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

int check(int x){
    //inedge 內部的 SE 大小，outedge 外部的 edge 大小，預設是最小
    int inedge = INF, outedge = 0; //inedge = inside edge, outedge = outside edge
    for(int i = 1; i <= n; i++){ //針對每一個邊仔細檢查
        if(x != find_root(i)) continue; //如果兩個生成樹並不一樣，表示內部沒有 SE

        for(auto it: edges[i]){ 
            //如果生成樹都一樣，那將內部最大 SE 取出
            if(find_root(it.first) == x) inedge = min(inedge, it.second);
            else outedge = max(outedge, it.second); //如果不一樣，那就表示這個邊並不是內部SE、而是外部 SE
        }
    }

    //cout << "x inedge outedge " << x << " " << inedge << " " << outedge << "\n";
    return inedge > outedge; //如果內部 SE 比外部大，表示這一個生成樹可以在組成一組 SE
}

int32_t main(){
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif // LOCAL
    cin >> t;
    while(t--){
        cin >> n >> m;
        node.clear();
        for(int i = 1; i <= n; i++){
            p[i] = i; //init disjoint set
            edges[i].clear();
            length[i] = 1;
        }

        for(int i = 0; i < m; i++){
            cin >> a >> b >> c; //輸入邊、成本
            node.push_back({a,b,c});
            edges[a].push_back({b,c});
            edges[b].push_back({a,c});
        }
        sort(node.begin(), node.end()); //排序，這邊排序方式為遞增

        int ans = 0;
        for(edge it: node){
            //cout << it.u << " " << it.v << " " << it.c << "\n";
            int pu = find_root(it.u); //判斷邊的節點們是否都在同個 set
            int pv = find_root(it.v);
            if(find_root(pu) != find_root(pv)){
                p[pv] = pu;
                length[pu] += length[pv]; //計入成本，表示以 pv 為頭的 SE，轉給 pu

                //cout << "len pu " << length[pu] << "\n";
                if(check(pu)) ans += length[pu]; //分析 3.3
            }

        }

        cout << ans << "\n";
    }
}