解題區/解題區 - Zerojudge

a458. Beats of the Angel 加強版

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

給一張圖，給定起點 S、終點 T，把任意邊的權重放大兩倍，請問最多能拉長最短道路長度為何。

意即修改一條邊找替代道路，使得替代道路越長越好。

Sample Input

1
2
3
4
5
6
7
8
9
5 7
2 1 5
1 3 1
3 2 8
3 5 7
3 4 3
2 4 7
4 5 2
1 5

Sample Output

1
2

Solution

終於向 liouzhou101 問到解法，類似 BZOJ 2725 Violet 6 故乡的梦，過了三年多，才把 Angel Beats 加強版寫出來，終於完成了，代碼是如此地迷人，一堆掃描線算法，找瓶頸也用掃描線代替感覺萌萌哒。

移除掉一條邊，找到 S-T 最短路徑的替代道路 $O(E \log E)$ 離線處理。

  1. 先在 DAG 上找瓶頸，只有瓶頸發生變化才受影響。
  2. 計算 DAG 上，經過瓶頸的最小次數。
  3. 接著，對瓶頸由近至遠進行掃描，維護一個最小堆 multiset，維護替代道路的可行性，保持掃描線左右兩方各自通過的瓶頸數接起來不會通過瓶頸。
1
2
3
4
5
       B -- C        H -- I
      /      \      /      \
S - A         D -- G ------ J - T
      \      /  
       E -- F

變數說明

  • Ds(u) 表示從起點 S 到 u 的最短路徑
  • De(u) 表示從 u 到終點 T 的最短路徑
  • Bs(u) 表示從起點 S 到 u 保持在最短路徑上，經過最少的瓶頸數
  • Be(u) 表示從 u 到終點 T 保持在最短路徑上，經過最少的瓶頸數

例如先找到 shortest-path DAG 圖如上，則 D - G 和 J - T 都是瓶頸。瓶頸有兩種找法，第一種是類似最大流的最小割，第二種是轉換成區間，例如 e(u, v) 則可以得到區間 [Ds(u), Ds(v)]，然後做掃描線算法，得到哪個時候只有一個區間，則那個邊就是瓶頸。

得到所有瓶頸後，依序掃描離 S 近到遠的瓶頸，維護一個 mutliset<int>，當窮舉瓶頸 e(u, v)，則替代道路為 min(Ds(a) + w(a, b) + De(b))，滿足 Bs(a) <= Bs(u) 和 Be(b) <= Be(v)。條件 Bs(a) <= Bs(u) 和 Be(b) <= Be(v) 是為了保證不經過這個瓶頸。

隨著掃描線移動，Be(b) 遞減，Bs(a) 遞增，因此先排序 Bs[] 和 Be[]，每當掃描到一個瓶頸，鬆弛新的路徑，同時移除掉最小堆中 Ds(a) + w(a, b) + De(b) 且 Be(b) > Be(v) 的所有元素。

英文名稱 The selfish-edges Shortest-Path problem

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
#include <bits/stdc++.h> 
using namespace std;
// http://zrt.github.io/2014/08/13/bzoj2725/
const int MAXV = 200005;
const int MAXE = 200005<<1;
const long long INF = 1LL<<60;
struct Edge {
    int to, eid;
    long long w;
    Edge *next;
};
Edge edge[MAXE], *adj[MAXV];
int e = 0;
long long Ds[MAXV], De[MAXV];
int Bs[MAXV], Be[MAXV], keye[MAXE];
void addEdge(int x, int y, long long v)  {
    edge[e].to = y, edge[e].w = v, edge[e].eid = e;
    edge[e].next = adj[x], adj[x] = &edge[e++];
    edge[e].to = x, edge[e].w = v, edge[e].eid = e;
    edge[e].next = adj[y], adj[y] = &edge[e++];
}
void dijkstra(int st, long long dist[], int n) {
typedef pair<long long, int> PLL;
    for (int i = 0; i <= n; i++)
        dist[i] = INF;
    set<PLL> pQ;
    PLL u;
    pQ.insert(PLL(0, st)), dist[st] = 0;
    while (!pQ.empty()) {
        u = *pQ.begin(), pQ.erase(pQ.begin());
        for (Edge *p = adj[u.second]; p; p = p->next) {
            if (dist[p->to] > dist[u.second] + p->w) {
                if (dist[p->to] != INF)
                    pQ.erase(pQ.find(PLL(dist[p->to], p->to)));
                dist[p->to] = dist[u.second] + p->w;
                pQ.insert(PLL(dist[p->to], p->to));
            }
        }
    }
}
int bottleneck(int st, int ed, long long Ds[], long long De[], int n) {
typedef pair<long long, pair<long long, int> > PLL;
    vector<PLL> A;
    // short path DAG st-ed
    long long d = Ds[ed];
    for (int i = 1; i <= n; i++) {
        for (Edge *p = adj[i]; p; p = p->next) {
            if (Ds[p->to] == Ds[i] + p->w && Ds[p->to] + De[p->to] == d) {
                A.push_back(PLL(Ds[i], {Ds[p->to], p->eid}));
            }
        }
    }
    // bottleneck edge st-ed
    sort(A.begin(), A.end());
    priority_queue<long long, vector<long long>, std::greater<long long>> pQ;
    int cnt = 0;
    for (int i = 0; i < e; i++)
        keye[i] = 0;
    for (int i = 0; i < A.size(); ) {
        long long l = A[i].first;
        while (!pQ.empty() && pQ.top() <= l)
            pQ.pop();
        while (i < A.size() && A[i].first <= l)
            pQ.push(A[i].second.first), i++;
        if (pQ.size() == 1) {
            keye[A[i-1].second.second] = 1;
            keye[A[i-1].second.second^1] = -1;
            cnt++;
        }
    } 
    return cnt;
}
void bfs(int st, int dist[], long long Ds[], int n, int f) {
typedef pair<long long, int> PLL;
    // work for short-path DAG, weight: key edge
    vector<PLL> A;
    for (int i = 1; i <= n; i++)
        A.push_back(PLL(Ds[i], i)), dist[i] = 0x3f3f3f3f;
    dist[st] = 0;
    sort(A.begin(), A.end());
    for (int i = 0; i < n; i++) {
        int x = A[i].second;
        for (Edge *p = adj[x]; p; p = p->next) {
            if (Ds[p->to] == Ds[x] + p->w)
                dist[p->to] = min(dist[p->to], dist[x] + (keye[p->eid] == f));
        }
    }
}
long long solve(int st, int ed, long long Ds[], long long De[], int n) {
typedef pair<long long, int> PLL;
typedef pair<int, int> PII;
typedef multiset<long long>::iterator MIT;
    bfs(st, Bs, Ds, n, 1);
    bfs(ed, Be, De, n, -1);
    vector<PLL> A;
    vector<PII> B, C;
    for (int i = 1; i <= n; i++) {
        A.push_back(PLL(Ds[i], i));
        B.push_back(PII(Bs[i], i));
        C.push_back(PII(Be[i], i));
    }
    sort(A.begin(), A.end());
    sort(B.begin(), B.end());
    sort(C.begin(), C.end());
    long long d = Ds[ed];
    int Bidx = 0, Cidx = n-1;
    multiset<long long> S;
    vector< vector<MIT> > RM(n+1, vector<MIT>());
    long long ret = 0;
    for (int i = 0; i < n; i++) {
        int x = A[i].second;
        for (Edge *p = adj[x]; p; p = p->next) {
            if (Ds[p->to] == Ds[x] + p->w && Ds[p->to] + De[p->to] == d) {
                if (keye[p->eid]) {
                    int bb = Bs[x], cut = Be[p->to];
                    // relax
                    for (; Bidx < B.size() && B[Bidx].first <= bb; Bidx++) {
                        int u = B[Bidx].second;
                        for (Edge *q = adj[u]; q; q = q->next) {
                            if (Be[q->to] <= cut && p != q) {
                                MIT it = S.insert(Ds[u] + q->w + De[q->to]);
                                RM[q->to].push_back(it);
                            }
                        }
                    }
                    // remove
                    for (; Cidx >= 0 && C[Cidx].first > cut; Cidx--) {
                        int u = C[Cidx].second;
                        for (auto e : RM[u])
                            S.erase(e);
                    }
                    long long replace_path = INF;
                    if (!S.empty())
                        replace_path = *S.begin();
                    replace_path = min(replace_path, d + p->w); // this edge double weight
                    ret = max(ret, replace_path - d);
                }
            }
        }
    }
    return ret;
}
int main() {
    int n, m, x, y;
    int st, ed;
    long long v;
    while (scanf("%d %d", &n, &m) == 2) {
        for (int i = 1; i <= n; i++)
            adj[i] = NULL;
        for (int i = 0; i < m; i++) {
            scanf("%d %d %lld", &x, &y, &v);
            addEdge(x, y, v);
        }
        scanf("%d %d", &st, &ed);
        dijkstra(st, Ds, n);
        dijkstra(ed, De, n);
        int cnt = bottleneck(st, ed, Ds, De, n);
        if (cnt == 0)
            puts("0");
        else
            printf("%lld\n", solve(st, ed, Ds, De, n));
    }
    return 0;
}