[[416100]]

本文轉(zhuǎn)載自微信公眾號「Piper蛋窩」，作者Piper蛋。轉(zhuǎn)載本文請聯(lián)系Piper蛋窩公眾號。

記錄一道題解, 題目來自 Acwing.com 第 11 場周賽.

https://www.acwing.com/activity/content/59/

沒參加. 如果讓我做的話我做不出來, 難度是困難, 不是一道模板題, 用的知識點(diǎn) bfs 啥的都簡單, 但是考的是分析能力.

我的筆記:

https://github.com/PiperLiu/ACMOI_Journey/tree/master/notes

最大化最短路[1]

給定一個 個點(diǎn) 條邊的無向連通圖。

圖中所有點(diǎn)的編號為 。

圖中不含重邊和自環(huán)。

指定圖中的 個點(diǎn)為特殊點(diǎn)。

現(xiàn)在，你必須選擇兩個特殊點(diǎn)，并在這兩個點(diǎn)之間增加一條邊。

所選兩點(diǎn)之間允許原本就存在邊。

我們希望，在增邊操作完成以后，點(diǎn) 到點(diǎn) 的最短距離盡可能大。

輸出這個最短距離的最大可能值。

注意，圖中所有邊(包括新增邊)的邊長均為 。

輸入格式

第一行包含三個整數(shù) 。

第二行包含 個整數(shù) ，表示 個特殊點(diǎn)的編號， 之間兩兩不同。

接下來 行，每行包含兩個整數(shù) ，表示點(diǎn) 和點(diǎn) 之間存在一條邊。

輸出格式

一個整數(shù)，表示最短距離的最大可能值。

數(shù)據(jù)范圍

前六個測試點(diǎn)滿足 。

所有測試點(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 

競賽中等難度題目，重點(diǎn)在分析。

分析第一步，分情況討論。

題目中要求，必須在特殊點(diǎn)中選擇兩個點(diǎn)，這兩個點(diǎn)之間會新增一條邊。優(yōu)化目標(biāo)是，新增邊后， 1 到 n 的最短路徑最大。

從 1 到 n 的最短路徑只可能有以下三種情況(如上圖)：

• 不經(jīng)過 a to b 這條線
• 經(jīng)過 a -> b ，則距離是 x[a] + 1 + y[b]
• 經(jīng)過 b -> a ，則距離是 x[b] + 1 + y[a]
• 說明：x[a] 為 1 到 a 的距離，y[b] 為 n 到 b 的距離

如果我們在 a 與 b 中增加一條邊，則最終最短路的距離為以下三者中取最小值：

• 原有最短路長度
• x[a] + 1 + y[b]
• x[b] + 1 + y[a]

我們沒辦法改變「原有最短路長度」，因此只能希望 min(x[a] + 1 + y[b], x[b] + 1 + y[a]) 這個值越大越好。

因此，我們要考慮所有特殊點(diǎn)的兩兩組合，然后，找出最大的 min(x[a] + 1 + y[b], x[b] + 1 + y[a]) 的 a b 組合。

找兩兩組合

我們沒法直接找 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] 時， 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] (這個約束條件也可使我們遍歷所有的 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 是一個指針 
    // 不可以用 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); 
     
    // 開始按照題解來，先按照 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;  // 對于第 b = 第一個點(diǎn)，a 也只能為第 0 個點(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); 
    } 
     
    // 最后與本來的最短路比較 
    res = min(res, dist1[n]); 
     
    printf("%d", res); 
} 

經(jīng)驗(yàn)：

這里，我們將數(shù)組傳入函數(shù) int dist[] ，不能使用 memset(dist, 0x3f, sizeof dist); 因?yàn)?dist 僅僅是一個指針，而非數(shù)組;我們的 dist 長度為 N ，且為 int 類型，因此 memset(dist, 0x3f, N * 4);

參考資料

[1]最大化最短路: https://www.acwing.com/problem/content/3800/