WiwiHo 的廢文專區

有各種廢文的地方

0%

APIO 2020 pB Swapping Cities

Posted on Edited on In

這題在 心得 有提到過了，覺得這題不錯而且我不知道現在要幹嘛所以來寫一篇。

題目大意

題目

有一張無向連通簡單圖，（）個點 （）條邊，都從 開始編號，邊有權重。

有 （）筆詢問，每筆詢問表示有兩台車分別在節點 和 ，這兩台車要分別要到節點 和 ，它們不能在同一時間在同個節點上，也不能同時經過某條邊（不一定所有時間都要移動），求兩台車經過的所有邊中，邊權最大的，最小可以是多少，可能無解。

強制在線。

子題：

  1. 圖成鏈或成環
  2. 圖是星狀圖，節點 是中間
  3. ，，
  5. 圖是一棵樹
  6. 無特殊限制

子題一

先討論什麼條件下會有解，兩台車不能交會，因為成本是「最大的邊」而不是花費的時間，所以可以先讓其中一台開到某個點等另一台開到不會擋路的地方，很直覺地可以想到圖是一條鏈就會做不到這件事。如果圖是一條鏈，那就可以想成這張圖是一條線，車是線上的兩個動點，因為這兩個點不能交會，所以它們的相對位置永遠不會改變，然而它們又要交換位置，顯然是不可能的。

這樣就可以得出這個子題的作法：如果圖是鏈就無解，如果是環的話，每一條邊都會經過，所以答案就是最大的權重。

子題二

星狀圖在 的時候還是一條鏈，這個狀況會無解，要先特判掉。

如果兩個起點都不是中心的話，就要找一個額外的點讓其中一輛車等待，找除了那兩個點以外，和中心相連的邊權重最小的那個點就好了，答案就是這三個點和中心相連的邊中，權重最大的。如果其中一個點是中心，就需要兩個額外的點（如下圖），相似地，找權重小的就好了。

子題三

不難發現到只要有上面那張圖的結構，也就是兩個起點所在的連通塊不是鏈就肯定有解，問題只有哪些邊可以滿足這個條件，並且其中最大的權重要盡量小，換句話說，我們想知道「權重不超過 的邊構成的圖能使兩個點所在的連通塊不是鏈」中的 最小可以是多少。

即然要 盡量小，那就先把邊都拿掉，然後按照邊權由小到大把邊加到圖上，再檢查兩個點是不是在同個連通塊和連通塊是不是鏈就好了，在這個子題可以暴力處理。判斷鏈有很簡單的方式，因為鏈中的點度數最多就是 2，所以有度數大於等於 3 的點就表示不是鏈，還有如果所有點的度數都是 2，那麼它就是環，所以是鏈的條件是「有點的度數大於 2 或沒有點的度數是 1」。每筆詢問都要重做，做一次是 ，時間複雜度是

子題四

延續上一個子題的想法，如果可以在 左右的時間做完一筆詢問，就可以過這個子題。

先想判斷兩個點是不是在同個連通塊的部分，顯然只要用 DSU 就可以解決了，而有沒有度數大於 2 或等於 1 的點也可以用 DSU 維護，只要記錄每個 set 有幾個點度數大於 2、幾個點度數等於 1，union 時相加，就可以維護好了。這樣複雜度是

滿分解

我對子題五沒有特別的想法（而且應該也對滿分解不太重要），所以就不寫了。

從限制來看， 左右的時間就要解決這題了，可以猜到應該是要預處理一些東西。

在 DSU 合併的時候，一般會讓其中一個 set 的根變成另一個的根，但這裡要改成新加一個點來當它們的根，這樣就可以在這個節點上記錄現在這個連通塊是不是鏈、最大的邊權是多少，這樣最後會得到一棵樹，葉節點都是原有的點、其他是新加的點。而如果要知道「兩個節點變連通時，連通塊是不是鏈、此時最大邊權為何」就只要找到讓它們連通的點，也就是它們的 LCA，要找到什麼時候連通塊才不是鏈，就從 LCA 往上找就好了，這可以簡單地一次 DFS 解決每個節點往上爬的答案，所以問題就變成 LCA 了。

注意到處理 DSU 時雖然不能啟發式合併，但仍然可以路徑壓縮，只要記好每個點真正的父節點就好了。

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
//#define NDEBUG
 
#include "swap.h"
 
#include <bits/stdc++.h>
#include <bits/extc++.h>
 
#define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define iter(a) a.begin(), a.end()
#define riter(a) a.rbegin(), a.rend()
#define lsort(a) sort(iter(a))
#define gsort(a) sort(riter(a))
#define pb(a) push_back(a)
#define eb(a) emplace_back(a)
#define pf(a) push_front(a)
#define pob pop_back()
#define pof pop_front()
#define mp(a, b) make_pair(a, b)
#define F first
#define S second
#define mt make_tuple
#define gt(t, i) get<i>(t)
#define iceil(a, b) ((a + b - 1) / b)
#define tomax(a, b) (a = max(a, b))
#define printv(a, b) {bool pvaspace=false; \
for(auto pva : a){ \
    if(pvaspace) b << " "; pvaspace=true;\
    b << pva;\
}\
b << "\n";}
 
//#define TEST
 
using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
 
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pdd = pair<ld, ld>;
using tiii = tuple<int, int, int>;
 
const ll MOD = 1000000007;
const ll MAX = 2147483647;
 
template<typename A, typename B>
ostream& operator<<(ostream& o, pair<A, B> p){
    return o << '(' << p.F << ',' << p.S << ')';
}
 
vector<int> dsu, one, three; //one=度數1的節點數量、three=度數>=3的節點數量
vector<vector<int>> anc, g;
vector<int> ans, in, out;

int findDSU(int a){
    if(dsu[a] != a) dsu[a] = findDSU(dsu[a]);
    return dsu[a];
}
 
void unionDSU(int a, int b){
    a = findDSU(a); b = findDSU(b);
    if(a == b) return;
    dsu[b] = a;
    one[a] += one[b];
    three[a] += three[b];
}
 
int dfsts = 0;
void dfs(int now, int p){
    in[now] = dfsts++;
    if(ans[now] == -1) ans[now] = ans[p];
    for(int i : g[now]) dfs(i, now);
    out[now] = dfsts++;
}
 
bool isAnc(int a, int b){
    return in[a] <= in[b] && out[a] >= out[b];
}
 
int lca(int a, int b){
    if(isAnc(a, b)) return a;
    for(int i = 19; i >= 0; i--){
        if(!isAnc(anc[a][i], b)) a = anc[a][i];
    }
    return anc[a][0];
}
 
 
void init(int N, int M,
          std::vector<int> U, std::vector<int> V, std::vector<int> W) {
 
    vector<pair<int, pii>> e(M);
    for(int i = 0; i < M; i++){
        e[i] = mp(W[i], mp(U[i], V[i]));
    }
    lsort(e);
 
    dsu.resize(N + M);
    for(int i = 0; i < N + M; i++) dsu[i] = i;
    one.resize(N + M); three.resize(N + M);
 
    int ts = N;
 
    anc.resize(N + M, vector<int>(20));
    for(int i = 0; i < N + M; i++) anc[i][0] = i;
    ans.resize(N + M, -1);
    g.resize(N + M);
    in.resize(N + M);
    out.resize(N + M);
 
    vector<int> deg(N);
 
    //加邊
    for(auto i : e){
        int w = i.F, u = i.S.F, v = i.S.S;
        //更新度數=1、>=3的節點數
        if(deg[u] == 1) one[findDSU(u)]--;
        if(deg[v] == 1) one[findDSU(v)]--;
        deg[u]++; deg[v]++;
        if(deg[u] == 1) one[findDSU(u)]++;
        else if(deg[u] == 3) three[findDSU(u)]++;
        if(deg[v] == 1) one[findDSU(v)]++;
        else if(deg[v] == 3) three[findDSU(v)]++;
 
        //合併
        u = findDSU(u);
        v = findDSU(v);
        int dv = ts++;
        if(u == v){ //如果本來就在同一個set，也加一個新的點當根
            unionDSU(dv, u);
            anc[u][0] = dv;
            g[dv].eb(u);
        }
        else{
            unionDSU(dv, u);
            unionDSU(dv, v);
            anc[u][0] = anc[v][0] = dv;
            g[dv].eb(u); g[dv].eb(v);
        }
 
        if(!one[dv] || three[dv]) ans[dv] = w;
    }
 
//    for(int i = 0; i < N + M; i++) cerr << anc[i][0] << " ";
//    cerr << "\n";
 
    for(int i = 0; i < N + M; i++){
        if(anc[i][0] == i) dfs(i, i);
    }
 
    for(int i = 1; i < 20; i++){
        for(int j = 0; j < N + M; j++){
            anc[j][i] = anc[anc[j][i - 1]][i - 1];
        }
    }
 
}
 
int getMinimumFuelCapacity(int X, int Y) {
    if(findDSU(X) != findDSU(Y)) return -1;
    return ans[lca(X, Y)];
}