733-F. Drivers Dissatisfaction

2021-03-15 19:45:33 +0800 CST Tags: disjoint-set, graph, minimum-spanning-tree

出處：https://codeforces.com/contest/733/problem/F
提交：https://codeforces.com/contest/733/submission/108298897

問題：給定 $n\in[2,2\cdot10^5]$ 個城市 (1 ~ n) 以及所有 $m\in[n-1,2\cdot10^5]$ 條道路它們的不舒服感 $w_i\in[1,10^9]$、一單位的金錢能減輕自己所造成的不舒服感量值 $c_i\in[1,10^9]$，以及自己所雙向連接的城市 $a_i$ 和 $b_i$ (其中 $a_i, b_i\in[1,n]$ 而且 $a_i\ne b_i$)。最後是能拿來改善不舒服感的總金額 $S\in[0,10^9]$。注意到一條道路的不舒服感量值可以是負的，變成舒服的意思？請問如何選出 n-1 條使得任意城市之間都彼此互相連通的道路 (其實就是 tree) 之後再把 S 全數拿來改善道路的不舒服感 [1]，能使得這 n-1 條道路的不舒服感總和最小？此時每一條道路的不舒服感分別為何？

解法：
吾人一看到此題型應立馬想到最小生成樹，只不過我們也很容易發現這題最難搞的就是那個 $c_i$。如果很幸運地最小的 $c_i$ 剛好就包在原本的生成樹裡面，那麼很當然地可以直接把 S 全部拿來改善 $c_i$ 這條路，但是如果最小的 $c_i$ 是落在生成樹外面呢？會不會正解的生成樹其實應該要包含那條邊，而不是我們原本找的樹呢？答案是肯定的，甚至如果說最小的 $c_i$ 所對應到的 $w_i$ 已經太大使得答案變差，也有可能得找第二小的 $c_i$ (理想上它的 $w_i$ 比較不會那麼大) 才是正解，或者是第三小的 $c_i$ 等等等。那麼現在問題就轉變成：如何修改原本的生成樹去得到確定包含某個在樹以外的 $c_i$ 的局部最佳解呢？

假設有包含 $c_i$ 的樹是我們暫時要的局部最佳解，那麼正確的修改方式便是直接挖掉從 $c_i$ 的兩端點開始在樹內形成的路徑之中那條最不舒服的邊 [2]，並替換成現在這個 $c_i$。完成這個動作之後，如果還想要再替換那棵樹的其他邊，都只會造成更差的解，這個結論直接由「最小」生成樹的定義就可以得到了。於是乎，從所有不同的 $c_i$ 所對應到的局部最佳解之中再取一個最小值，就是我們的全域最佳解。

附註：
[1] 這題在金錢的計算上有小瑕疵，一般來說把全部的金錢拿去改善唯一一條有最小 $c_i$ 的邊會是最佳策略，只不過這題的 $S / c_i$ 未必會整除，此時預設答案應該是「沒有」把餘數 (剩下來的金額) 繼續拿去其他還沒有改善過的道路，但是這條有最小 $c_i$ 的道路改善的不舒服感仍然只是商數，於是那些剩下來的金額就這樣憑空消失了？
[2] 其實有一個方法可以在建構最小生成樹的過程中就能順便找到每條邊的兩端點在樹內形成的路徑之中具有最大權重的邊，詳細的實作與證明可參考 xxx。

實作：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56


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

long long n, base;
int length, m, d, s, noe;
int p[200000], g[200000], dis[200000], disId[200000], c[200000], a[200000], b[200000], rmeId[200000], ans[200000];
set<int> exeId[200000]; // external edge ids

int find(int v) {
    return v == p[v] ? v : p[v] = find(p[v]);
}

int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
    cin >> n >> m;
    for (int i=0; i<n; i++) p[i] = i, g[i] = 1; // disjoint-set forest
    for (int i=0; i<m; i++) cin >> dis[i], disId[i] = i;
    for (int i=0; i<m; i++) cin >> c[i];
    for (int i=0; i<m; i++) { int x, y;
        cin >> x >> y; x--; y--;
        exeId[x].insert(i); exeId[y].insert(i);
        a[i] = x; b[i] = y;
    }
    cin >> s;
    sort(disId, disId+m, [](int a, int b){ return dis[a] < dis[b]; }); int noe = 0; // number of edges
    for (int i=0; i<m && noe<n-1; i++) {
        int eid = disId[i], x = find(a[eid]), y = find(b[eid]);
        if (x != y) { noe++;
            if (g[x] < g[y]) swap(x, y);
            p[y] = x; g[x] += g[y];
            for (auto eid2: exeId[y]) {
                if (exeId[x].find(eid2) == exeId[x].end()) exeId[x].insert(eid2);
                else {
                    rmeId[eid2] = eid;
                    exeId[x].erase(eid2);
                }
            }
            exeId[y].clear(); // comment out for efficiency
            base += dis[eid];
            ans[length++] = eid;
        }
    }
    n = LLONG_MAX; // used as the minimum difference
    for (int i=0; i<m; i++) {
        if (n > dis[i] - s/c[i] - dis[rmeId[i]]) {
            n = dis[i] - s/c[i] - dis[rmeId[i]];
            d = i;
        }
    }
    cout << base + n << endl;
    for (int i=0; i<length; i++) {
        int eid = ans[i];
        if (eid != rmeId[d]) cout << eid+1 << " " << dis[eid] << endl;
    }
    cout << d+1 << " " << dis[d] - s/c[d] << endl;
    return 0;
}

結果： Example image