UVa10457 - Magic Car(Kruskal)

題目大意

有一台神奇的車子，稱呼為 magic car

• 發動跟結束都需要耗費能量
• 中間距離所使用的能量是這樣計算的：\(max(每一條街最大的能量) - min(每一條街最大的能量\)
  現在這台車子要從 A 到 B，會經過許多條路，請你告訴我走最省油的路徑抵達 B 點時，會花多少能量

題目連結

重點觀念

• 如何確定 \(max(每一條街最大的能量) - min(每一條街最大的能量\) 最佳化

分析

• 首先我們將公式進行解析，\(max(每一條街最大的能量)\) 可以用 Kruskal 找出來
  • 判斷 A 與 B 是否在同個最小生成樹，當 A 與 B 在同個生成樹時使用的最後一個邊，可以知道是 \(max(每一條街最大的能量)\)
    因為 kruskal 會從最小的邊開始累積
• \(min(每一條街最大的能量\) 由於 Kruskal 都是從最小的開始找、並且題目的邊不大於 1000，因此我們使用暴力。
  • 從最小的邊開始，不斷找出生成樹，並讓 \(生成樹最大邊 - 最小的邊能量\)，並找出最小的答案即可。

參考連結

UVA 10457 - Magic Car(最小瓶颈路) by lab104_yifan
最小瓶颈路含义 by csdn

題目程式碼

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

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

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define MAXN 200020
#define int long long
#define INF 0x3f3f3f
using namespace std;
int t, n, m, q;
int a, b, c;
int start, destination;
int ca, cb;
int p[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;
vector<edge> MST; //最小生成樹

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

void kruskal(){
    node.clear();
    MST.clear();

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

    cin >> ca >> cb;


    cin >> q;
    while(q--){
        int ans = INF;
        cin >> start >> destination;
        for(int i = 0; i < m; i++){ //分析 2-1
            for(int j = 1; j <= n; j++) p[j] = j; //init disjoint set

            for(int k = i; k < m; k++){
                edge it = node[k];
                //cout << it.u << " " << it.v << " " << it.c << "\n";
                //cout << p[3] << " " << p[4] << "\n";
                int pu = find_root(it.u); //判斷邊的節點們是否都在同個 set
                int pv = find_root(it.v);
                if(pu != pv) p[pv] = pu;

                //如果這個邊可讓這兩個節點都在同個生成樹，那就是最大邊
                if(find_root(start) == find_root(destination)){ 
                    ans = min(it.c - node[i].c, ans);
                    break;
                }
            }
        }
        cout << ans + ca + cb << "\n";
    }
}

int32_t main(){
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
#endif // LOCAL
    kruskal();
}