最短路怎么可能盡可能地長(zhǎng)呢?
本文轉(zhuǎn)載自微信公眾號(hào)「Piper蛋窩」，作者Piper蛋。轉(zhuǎn)載本文請(qǐng)聯(lián)系Piper蛋窩公眾號(hào)。
記錄一道題解, 題目來(lái)自 Acwing.com 第 11 場(chǎng)周賽.
https://www.acwing.com/activity/content/59/
沒(méi)參加. 如果讓我做的話我做不出來(lái), 難度是困難, 不是一道模板題, 用的知識(shí)點(diǎn) bfs 啥的都簡(jiǎn)單, 但是考的是分析能力.
我的筆記:
https://github.com/PiperLiu/ACMOI_Journey/tree/master/notes
最大化最短路[1]
給定一個(gè) 個(gè)點(diǎn) 條邊的無(wú)向連通圖。
圖中所有點(diǎn)的編號(hào)為 。
圖中不含重邊和自環(huán)。
指定圖中的 個(gè)點(diǎn)為特殊點(diǎn)。
現(xiàn)在，你必須選擇兩個(gè)特殊點(diǎn)，并在這兩個(gè)點(diǎn)之間增加一條邊。
所選兩點(diǎn)之間允許原本就存在邊。
我們希望，在增邊操作完成以后，點(diǎn) 到點(diǎn) 的最短距離盡可能大。
輸出這個(gè)最短距離的最大可能值。
注意，圖中所有邊(包括新增邊)的邊長(zhǎng)均為 。
輸入格式
第一行包含三個(gè)整數(shù) 。
第二行包含 個(gè)整數(shù) ，表示 個(gè)特殊點(diǎn)的編號(hào)， 之間兩兩不同。
接下來(lái) 行，每行包含兩個(gè)整數(shù) ，表示點(diǎn) 和點(diǎn) 之間存在一條邊。
輸出格式
一個(gè)整數(shù)，表示最短距離的最大可能值。
數(shù)據(jù)范圍
前六個(gè)測(cè)試點(diǎn)滿足 。
所有測(cè)試點(diǎn)滿足 ，，，，。
輸入樣例1：
- 5 5 3
- 1 3 5
- 1 2
- 2 3
- 3 4
- 3 5
- 2 4
輸出樣例1：
- 3
輸入樣例2：
- 5 4 2
- 2 4
- 1 2
- 2 3
- 3 4
- 4 5
輸出樣例2：
- 3
競(jìng)賽中等難度題目，重點(diǎn)在分析。
分析第一步，分情況討論。
題目中要求，必須在特殊點(diǎn)中選擇兩個(gè)點(diǎn)，這兩個(gè)點(diǎn)之間會(huì)新增一條邊。優(yōu)化目標(biāo)是，新增邊后， 1 到 n 的最短路徑最大。
從 1 到 n 的最短路徑只可能有以下三種情況(如上圖)：
- 不經(jīng)過(guò) a to b 這條線
- 經(jīng)過(guò) a -> b ，則距離是 x[a] + 1 + y[b]
- 經(jīng)過(guò) b -> a ，則距離是 x[b] + 1 + y[a]
- 說(shuō)明：x[a] 為 1 到 a 的距離，y[b] 為 n 到 b 的距離
如果我們?cè)?a 與 b 中增加一條邊，則最終最短路的距離為以下三者中取最小值：
- 原有最短路長(zhǎng)度
- x[a] + 1 + y[b]
- x[b] + 1 + y[a]
我們沒(méi)辦法改變「原有最短路長(zhǎng)度」，因此只能希望 min(x[a] + 1 + y[b], x[b] + 1 + y[a]) 這個(gè)值越大越好。
因此，我們要考慮所有特殊點(diǎn)的兩兩組合，然后，找出最大的 min(x[a] + 1 + y[b], x[b] + 1 + y[a]) 的 a b 組合。
找兩兩組合
我們沒(méi)法直接找 min(x[a] + 1 + y[b], x[b] + 1 + y[a]) 的最大值，得進(jìn)行一步推導(dǎo)：
- x[a] + 1 + y[b] <= x[b] + 1 + y[a]
- 即 x[a] - y[a] <= x[b] - y[b]
- 即，當(dāng) x[a] - y[a] <= x[b] - y[b] 時(shí)， min(x[a] + 1 + y[b], x[b] + 1 + y[a]) 為 x[a] + 1 + y[b]
- 即，我們找 a, b 滿足 x[a] - y[a] <= x[b] - y[b] (這個(gè)約束條件也可使我們遍歷所有的 a, b 組合)，使得 x[a] + 1 + y[b] 最大
找兩兩組合
如上，我們將特殊的點(diǎn)按照 x[i] - y[i] 升序排序;我們令 b 為第一層循環(huán)：即首先確定 b 的位置(圖中為 i ) ， a 的話，選擇選擇從起點(diǎn)到 i 的最大值即可，因?yàn)槲覀兊哪繕?biāo)是圖中紅色的線值最大，即 y[b] + 1 + x[a] 。
- #include <iostream>
- #include <cstring>
- #include <algorithm>
- using namespace std;
- const int N = 2e5 + 10, M = 4e5 + 10;
- int n, m, k;
- int a[N], dist1[N], dist2[N]; // 特殊點(diǎn)，題解中的x[]和y[]
- int h[N], e[M], ne[M], idx;
- int q[N]; // bfs 用的隊(duì)列
- void add(int a, int b)
- {
- e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
- }
- void bfs(int st, int dist[])
- {
- int tt = 0, hh = 0;
- q[0] = st;
- // 傳入?yún)?shù)的 dist 是一個(gè)指針
- // 不可以用 sizeof dist
- memset(dist, 0x3f, 4 * N);
- dist[st] = 0;
- while (hh <= tt)
- {
- int t = q[hh ++];
- // printf("t = %d h[t] = %d \n", t, h[t]);
- for (int i = h[t]; ~i; i = ne[i])
- {
- int j = e[i];
- if (dist[j] > dist[t] + 1)
- {
- dist[j] = dist[t] + 1;
- // printf("dist[%d] = %d t = %d\n", j, dist[j], tt);
- q[++ tt] = j;
- }
- }
- }
- }
- int main()
- {
- scanf("%d%d%d", &n, &m, &k);
- memset(h, -1, sizeof h); // 莫忘！
- for (int i = 0; i < k; ++ i)
- {
- scanf("%d", &a[i]);
- }
- for (int i = 0; i < m; ++ i)
- {
- int x, y;
- scanf("%d%d", &x, &y);
- add(x, y);
- add(y, x);
- }
- bfs(1, dist1);
- // printf("==bfs2\n");
- bfs(n, dist2);
- // 開(kāi)始按照題解來(lái)，先按照 dist1[i] - dist2[i] 排序
- sort(a, a + k, [&](int a, int b "&") {
- return dist1[a] - dist2[a] < dist1[b] - dist2[b];
- });
- // b 作為最外層循環(huán)，找最大的 dist1[a] + 1 + dist2[b]
- int x = dist1[a[0]], res = 0; // 對(duì)于第 b = 第一個(gè)點(diǎn)，a 也只能為第 0 個(gè)點(diǎn)（這里 x 是題解中紅線的左上端點(diǎn)）
- for (int i = 1; i < k; i ++ )
- {
- int t = a[i]; // 這里 dist2[t] 是題解中紅線的右下端點(diǎn)
- res = max(res, dist2[t] + 1 + x);
- x = max(dist1[t], x);
- }
- // 最后與本來(lái)的最短路比較
- res = min(res, dist1[n]);
- printf("%d", res);
- }
經(jīng)驗(yàn)：
這里，我們將數(shù)組傳入函數(shù) int dist[] ，不能使用 memset(dist, 0x3f, sizeof dist); 因?yàn)?dist 僅僅是一個(gè)指針，而非數(shù)組;我們的 dist 長(zhǎng)度為 N ，且為 int 類型，因此 memset(dist, 0x3f, N * 4);
參考資料
[1]最大化最短路: https://www.acwing.com/problem/content/3800/
