UVA 00908 - Re-connecting Computer Sites

解題觀念

Disjoint Set - MST
可以參考我的課程簡報：MST & Shortest Path

Disjoint Set

關於 Disjoint Set 的基本觀念可以參考我的這篇文章：Algorithm - Disjoint Set

Minimum Spanning Tree Kruskal’s Algorithm

關於 Minimum Spanning Tree Kruskal’s Algorithm 的基本觀念可以參考我的這篇文章：Algorithm - Minimum Spanning Tree Kruskal’s Algorithm

題目敘述

電腦線路連接

今天給你一些電腦線路連接的狀態，以及原來選取的網路線
現在基於此基礎上加入了 K 條捷徑線路，而原有的全部可用線路有 M 條
請幫忙連接線路，使電腦彼此接連通且線路長度和最小

Input

每組輸入中
第一行為數字 n,代表有多少電腦

接下來 n-1 行表示目前連接狀態的線路
有三個數 u、v、w 表示線段兩端連接的電腦及線路長度

再來給予數字 K,代表新給予的線路
接下來 K 行有三個數 u、v、w 表示新線段兩端連接的電腦及線路長度

最後給予數字 M,代表所有可用線路
接下來 M 行有三個數 u、v、w 表示原線段兩端連接的電腦及線路長度

5
1 2 5
1 3 5
1 4 5
1 5 5
1
2 3 2
6
1 2 5
1 3 5
1 4 5
1 5 5
3 4 8
4 5 8

Output

每組輸出中
第一行輸出原連接狀態的線路長度
第二行輸出考慮新線路後的最短線路連接長度

20
17

Solution Code

#include<bits/stdc++.h>
using namespace std;

const int maxn = 1000000+5;

struct Edge{
    int u;
    int v;
    int w;

    bool operator < (const Edge &rhs) const{
        return w < rhs.w;
    }
};

int N, M;
int total = 0; // 紀錄最小生成樹的權重總和
int parent[maxn];
vector<Edge> edge;

// disjoint set
int find(int x){
    if(parent[x] < 0) return x;
    return parent[x] = find(parent[x]);
}

void Union(int a, int b){
    a = find(a);
    b = find(b);

    if(a != b){
        if(parent[a] < parent[b]){
            parent[a] += parent[b];
            parent[b] = a;
        }
        else{
            parent[b] += parent[a];
            parent[a] = b;
        }
    }
}

void kruskal(){
    // 先讓所有人父節點都是 -1 (沒有父親)
    memset(parent, -1, sizeof(parent));
    sort(edge.begin(), edge.end());

    int i, j;
    total = 0;
    // i < N-1 因為一顆樹最多只會有 N (點的數量) -1 條邊
    // j < M (M 是目前測資給予的邊的總數量 可能會有重邊 所以可能不只 N-1 條邊)
    for(i = 0, j = 0; i < N-1 && j < M; ++i){
        // 如果 u 和 v 的祖先相同 則 ++j (祖先相同會產生環 所以不要建立邊)
        while(find(edge[j].u) == find(edge[j].v)) ++j;

        // 若不會產生環 則讓兩點之間產生橋 (連接兩顆子生成樹)
        Union(edge[j].u, edge[j].v);
        total += edge[j].w;
        ++j;
    }
}

int main(){
    bool space = false;
    while(cin >> N){
        if(space) cout << endl;
        space = true;

        int u, v, w;
        total = 0;
        for(int i = 0; i < N-1; ++i){
            cin >> u >> v >> w;
            total += w;
        }
        cout << total << endl;

        int K;
        cin >> K;
        for(int i = 0; i < K; ++i){
            cin >> u >> v >> w;
            edge.push_back({u, v, w});
        }
        
        cin >> M;
        for(int i = 0; i < M; ++i){
            cin >> u >> v >> w;
            edge.push_back({u, v, w});
        }

        M = K + M;
        kruskal();

        cout << total << endl;
        while(!edge.empty()) edge.pop_back();
    }

}