凡是認(rèn)真刷過OD機(jī)試圖論題的人看到【Alice的安全旅行】這個(gè)名字多半會(huì)心一笑。題目包裝得再溫馨內(nèi)核依舊是最經(jīng)典的“最小瓶頸路”問題。我拿到2026雙機(jī)位C卷的時(shí)候這道題排在中后段一眼看過去以為又是普通最短路真上手才發(fā)現(xiàn)如果按慣性思維寫Dijkstra求邊權(quán)和答案會(huì)錯(cuò)得很離譜。這道題特別適合用來練“題目模型翻譯”能力它把圖論里非常成熟的“讓路徑上的最大邊權(quán)最小”抽象成旅行安全場(chǎng)景。無論你最終是否會(huì)遇到原題把它徹底吃透以后看到“降低最大風(fēng)險(xiǎn)”“限制單次消耗”“控制最大跳數(shù)”這類描述基本上都是同一套打法。這篇文章我會(huì)把題意、三種解法、完整C代碼、考場(chǎng)踩坑經(jīng)驗(yàn)一次性講清楚。1. 題目到底在說什么從故事到模型的翻譯1.1 題意速覽原題講的是旅行者在城市間移動(dòng)的事情大意可以還原成下面這個(gè)模型Alice生活的國(guó)家有N座城市編號(hào)從1到N城市之間一共有M條雙向道路。每條道路有一個(gè)危險(xiǎn)等級(jí)ww越大代表這條路越危險(xiǎn)。Alice從城市1出發(fā)想去城市N。她只關(guān)心一件事整條路線里最危險(xiǎn)的那一段不要超出自己的承受范圍?，F(xiàn)在要幫她求出這個(gè)“最小的最大危險(xiǎn)等級(jí)”是多少。如果城市1和城市N之間根本沒有任何通路輸出-1。輸入格式很直接第一行兩個(gè)整數(shù) N、M接下來 M 行每行三個(gè)整數(shù) u、v、w表示 u 和 v 之間存在一條危險(xiǎn)等級(jí)為 w 的雙向道路輸出一個(gè)整數(shù)就是所有從1到N的路徑中每條路徑上最大邊權(quán)的最小值。數(shù)據(jù)范圍通常是 N、M 都能到 10^5w 可以到 10^9 量級(jí)。所以別指望用 O(N^2) 的樸素算法必須往 O((NM)logW) 或者 O(MlogM) 這個(gè)方向想。1.2 這道題為什么不能直接套最短路徑很多人拿到題的第一反應(yīng)是“求最短路徑”因?yàn)槠綍r(shí)練得最多的就是Dijkstra及其各種變體。但注意這里不是求路徑上的邊權(quán)之和而是求路徑上所有邊權(quán)中的最大值最小。用一個(gè)只有三個(gè)城市的例子就能看出差別道路1城市1到城市2危險(xiǎn)等級(jí) 100道路2城市2到城市3危險(xiǎn)等級(jí) 100道路3城市1到城市3危險(xiǎn)等級(jí) 150從1到3有兩條路路徑A1 → 2 → 3邊權(quán)和 200最大邊權(quán) 100路徑B1 → 3邊權(quán)和 150最大邊權(quán) 150如果按普通最短路去寫Dijkstra會(huì)認(rèn)為路徑B更優(yōu)因?yàn)榭偤?50小于200輸出150。但題目真正問的是“最大危險(xiǎn)等級(jí)最小”路徑A雖然繞路但全程最危險(xiǎn)的一段只有100明顯更符合Alice的需求正確答案應(yīng)該是100。這就是這類題最陰險(xiǎn)的地方場(chǎng)景包裝讓你以為要算“總危險(xiǎn)度”實(shí)際考的是“瓶頸最小化”。理解錯(cuò)模型代碼寫得再漂亮也是白搭。1.3 難度評(píng)估與考點(diǎn)定位這道題在機(jī)試體系里屬于200分檔通常放在第三題或第四題的位置。它考的并不只是某一個(gè)模板而是三件事的組合能否把故事描述抽象成圖模型是否理解“最小值最大/最大值最小”問題的常規(guī)解法——二分答案是否掌握?qǐng)D連通性驗(yàn)證、并查集、最短路變種等基礎(chǔ)算法從考場(chǎng)表現(xiàn)看這道題的迷惑性很強(qiáng)。能一眼看出是“最小瓶頸路”的選手基本十分鐘能寫完被名字帶偏去寫普通最短路的往往要繞一個(gè)大彎才意識(shí)到問題。真正考試的時(shí)候如果發(fā)現(xiàn)樣例能過但總覺得哪里不對(duì)勁就要回頭重新讀題看看是不是把“最大邊權(quán)最小化”理解成了“邊權(quán)和最小化”。2. 三種主流解法誰最穩(wěn)誰最優(yōu)誰最短2.1 解法一二分答案 BFS/DFS 驗(yàn)證遇到“最小化最大值”或者“最大化最小值”第一反應(yīng)就應(yīng)該是二分答案這是考場(chǎng)上最穩(wěn)、最不容易出錯(cuò)的打法。為什么能二分關(guān)鍵在于單調(diào)性。假設(shè)我們給Alice設(shè)置一個(gè)可承受的最大危險(xiǎn)等級(jí) limit那么她走的路只能由危險(xiǎn)等級(jí)不超過 limit 的道路組成。limit 越大可選的道路就越多從城市1到達(dá)城市N的可能性只增不減limit 越小可選的道路就越少能走通的可能性只減不增。這種“隨著limit增大可行性單調(diào)變化”的性質(zhì)正是二分答案的前提。具體流程是這樣二分下界 l 設(shè)為0上界 r 設(shè)為所有邊中最大的危險(xiǎn)等級(jí)每次取 mid (l r) / 2調(diào)用 check(mid) 判斷只用危險(xiǎn)等級(jí)不超過 mid 的邊能否從1走到N如果能走通說明答案不高于 mid記錄 ans mid然后把 r 縮小到 mid - 1如果走不通說明 mid 還不夠大把 l 增大到 mid 1最后如果沒有記錄到任何 ans說明不連通輸出-1check 函數(shù)非常好寫。建好圖之后從節(jié)點(diǎn)1做一次 BFS 或者 DFS只訪問那些邊權(quán)不大于 mid 的鄰居看能不能碰到節(jié)點(diǎn)N就行。這里不涉及最短步數(shù)、不涉及權(quán)重累加只關(guān)心連通性所以隊(duì)列做 BFS 完全夠用。復(fù)雜度也很好看每次 check 是 O(NM)二分的次數(shù)大約是 O(log W)W是邊權(quán)值域。整體 O((NM)logW)對(duì)于 10^5 量級(jí)的輸入毫無壓力。2.2 解法二并查集 邊權(quán)排序第二種思路在競(jìng)賽圈叫“Kruskal 式加邊”乍一看和最小生成樹關(guān)系很大實(shí)際上只是借用了并查集維護(hù)連通分量的能力。做法如下把所有邊按照危險(xiǎn)等級(jí)從小到大排序然后一條一條地加入圖中。這里我們不需要真的建圖只需要維護(hù)一個(gè)并查集每次把當(dāng)前邊的兩個(gè)端點(diǎn)合并。每加完一條邊就檢查一下節(jié)點(diǎn)1和節(jié)點(diǎn)N是否已經(jīng)在同一個(gè)集合里。一旦它們連通了當(dāng)前這條邊的危險(xiǎn)等級(jí)就是答案。為什么這個(gè)貪心是對(duì)的因?yàn)槲覀兪前催厵?quán)遞增的順序加邊的。假設(shè)加到某條邊的時(shí)候1和N第一次連通了說明在此之前所有比這條邊權(quán)更小的邊組成的子圖里1和N是不連通的。也就是說任何從1到N的路徑都必須至少包含一條權(quán)值不小于當(dāng)前邊權(quán)的邊。既然如此最小可能的最大邊權(quán)恰好就是當(dāng)前這條邊的權(quán)值。這個(gè)證明可以自己在紙上畫一畫會(huì)比任何解釋都有說服力。復(fù)雜度方面排序是 O(MlogM)并查集的操作近似 O(M)整體就是 O(MlogM)。如果內(nèi)存和時(shí)限允許這個(gè)寫法在思路上最清爽代碼量也比二分BFS少一些核對(duì)起來很舒服。2.3 解法三Dijkstra 變形求瓶頸第三種寫法代碼量最短但需要你對(duì)Dijkstra的原理有比較透徹的理解。普通Dijkstra維護(hù)的是“到達(dá)某個(gè)點(diǎn)的路徑權(quán)值和的最小值”轉(zhuǎn)移時(shí)用 dis[u] w 去更新 dis[v]。這里我們改一下維護(hù)目標(biāo)dis[u] 表示“到達(dá)城市u的所有路徑中路徑上最大邊權(quán)的最小值”。轉(zhuǎn)移時(shí)不再是加法而是用 max(dis[u], w) 去更新 dis[v]。其他部分完全照搬Dijkstra優(yōu)先隊(duì)列小頂堆每次彈出當(dāng)前 dis 最小的節(jié)點(diǎn)去松弛鄰居。正確性的直覺可以這樣理解假設(shè)已經(jīng)知道從1到u的最優(yōu)瓶頸是 dis[u] 這么大那么從1經(jīng)過u再走一條邊權(quán)為w的邊到v整條路徑的瓶頸就是 max(dis[u], w)。如果這個(gè)值比目前已知的 dis[v] 更小就說明找到了一條更優(yōu)的到達(dá)v的路線應(yīng)該更新掉。用優(yōu)先隊(duì)列保證先處理的是瓶頸值最小的節(jié)點(diǎn)后續(xù)松弛一定不會(huì)比之前的更差這正是Dijkstra框架適用的條件。復(fù)雜度是 O(MlogN)和普通Dijkstra完全一致。這個(gè)寫法最精簡(jiǎn)但是對(duì)“為什么可以這樣做”的理解要求比較高如果只是套模板很難想到要把加號(hào)換成max。3. C 實(shí)現(xiàn)全解析3.1 二分BFS版本的完整可提交代碼三種解法中我最推薦考場(chǎng)上寫二分BFS因?yàn)樗悸分卑住⒉灰讓戝e(cuò)、邊界清楚。下面是一份可以直接提交的C實(shí)現(xiàn)#include bits/stdc.h using namespace std; const int MAXN 100005; vectorpairint, int g[MAXN]; int n, m; bool check(int limit) { vectorchar vis(n 1, 0); queueint q; q.push(1); vis[1] 1; while (!q.empty()) { int u q.front(); q.pop(); if (u n) return true; for (auto e : g[u]) { int v e.first; int w e.second; if (!vis[v] w limit) { vis[v] 1; q.push(v); } } } return false; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin n m; int maxw 0; for (int i 0; i m; i) { int u, v, w; cin u v w; g[u].push_back({v, w}); g[v].push_back({u, w}); maxw max(maxw, w); } int l 0, r maxw; int ans -1; while (l r) { int mid (l r) 1; if (check(mid)) { ans mid; r mid - 1; } else { l mid 1; } } cout ans \n; return 0; }如果你確定考場(chǎng)的編譯器支持C17for (auto [v, w] : g[u])這種結(jié)構(gòu)化綁定的寫法會(huì)更簡(jiǎn)潔。但說實(shí)話現(xiàn)場(chǎng)跑題的時(shí)候我不太建議冒險(xiǎn)用pair的first和second是最保險(xiǎn)的兼容所有常見環(huán)境。3.2 關(guān)鍵代碼動(dòng)作逐個(gè)拆解建圖部分要注意無向邊必須加兩條。很多人只會(huì)寫g[u].push_back({v, w})忘掉g[v].push_back({u, w})結(jié)果樣例運(yùn)氣好能過換一組數(shù)據(jù)直接白給。每一對(duì)輸入的 u、v、w都要對(duì)稱存儲(chǔ)。這是圖論題的老坑每次都得提醒自己。二分邊界也有講究。下界 l 我從0開始因?yàn)檫厵?quán)都是正數(shù)0不會(huì)是一個(gè)真正可行的上限值但作為二分起點(diǎn)完全沒問題。上界 r 直接取所有邊權(quán)中的最大值因?yàn)槿魏我粭l路徑的瓶頸都不可能超過整張圖的最大邊權(quán)。如果你圖省事把 r 設(shè)成一個(gè)很大的常數(shù)比如 10^9也不是不行但會(huì)白白增加幾次 check 調(diào)用稍微有點(diǎn)浪費(fèi)。check 函數(shù)里vis數(shù)組的作用是防止節(jié)點(diǎn)重復(fù)入隊(duì)。這里的 vis 是一個(gè) char 數(shù)組而不是 bool 數(shù)組純粹是為了省一點(diǎn)內(nèi)存也可以寫成 bool。BFS 一旦在隊(duì)列中碰到節(jié)點(diǎn) N 就立刻返回 true因?yàn)轭}目只問連通性不要求最短路徑所以不用統(tǒng)計(jì)步數(shù)也不需要等整層擴(kuò)展完。二分的循環(huán)條件是l r每次 check 成功時(shí)記錄 ans 并把右邊界收縮失敗時(shí)把左邊界抬高。循環(huán)結(jié)束后如果 ans 仍然是 -1說明在任何 limit 下都不連通輸出 -1 即可。3.3 多組測(cè)試用例實(shí)測(cè)拿幾組數(shù)據(jù)實(shí)測(cè)一下這段代碼順便演示推理過程。第一組樣例4 4 1 2 5 2 3 3 3 4 2 1 4 8圖中兩條路徑1→2→3→4 的最大邊權(quán)是 max(5,3,2)51→4 直連的最大邊權(quán)是 8。最優(yōu)答案是 5。二分過程會(huì)先嘗試 mid4此時(shí) 5、3、2 三條邊都不超過4但節(jié)點(diǎn)2到節(jié)點(diǎn)3的邊權(quán)為3、節(jié)點(diǎn)3到節(jié)點(diǎn)4的邊權(quán)為2整體能走到4嗎路線1→2需要邊權(quán)5超過4走不通所以 check(4) 返回 false。接著嘗試 mid5所有邊都能走check(5) 返回 true答案記錄為5繼續(xù)嘗試更小的值也沒能成功最終輸出5。第二組樣例3 1 1 2 5只有一條連接1和2的邊節(jié)點(diǎn)3孤立。無論 limit 多大BFS 都到不了3二分過程中 check 永遠(yuǎn)返回 falseans 保持 -1輸出 -1。這個(gè)用例驗(yàn)證的是不可達(dá)場(chǎng)景。第三組樣例5 5 1 2 9 2 5 9 1 3 4 3 4 4 4 5 41→2→5 的瓶頸是91→3→4→5 的瓶頸是4所以答案4。二分時(shí)先用 mid 像4這樣的值1→3→4→5 剛好全通check 成功記錄4之后嘗試更小值如3或2時(shí)1無法連接到任何節(jié)點(diǎn)失敗最終輸出4。這三組用例覆蓋了普通連通、不可達(dá)、多路徑繞行三種常見情況實(shí)測(cè)代碼輸出都正確。4. 實(shí)戰(zhàn)中踩過的坑與調(diào)試心得4.1 六個(gè)容易翻車的細(xì)節(jié)第一個(gè)坑就是無向圖只建單向邊。我見過太多人栽在這里尤其樣例比較巧的時(shí)候漏一條反向邊照樣能過。所有圖論題只要題目說“雙向道路”“無向圖”建圖時(shí)就必須雙向添加。寫完代碼后第一時(shí)間檢查g[u].push_back后面是不是跟著g[v].push_back。第二個(gè)坑是二分上界沒取好。有些人習(xí)慣把 r 定義成 1e9然后 mid 也會(huì)很大check 次數(shù)太多雖然不至于超時(shí)但代碼看起來不夠嚴(yán)謹(jǐn)。正確的做法是讀邊的時(shí)候維護(hù) maxw直接把右邊界設(shè)為 maxw。如果題目里 w 可能高達(dá) 10^9用 int 也放得下但保險(xiǎn)起見建議直接用 long long 存 w 和 mid。第三個(gè)坑是 BFS 沒有標(biāo)記訪問就入隊(duì)。這會(huì)導(dǎo)致同一個(gè)節(jié)點(diǎn)反復(fù)入隊(duì)輕則多刷很多無效遍歷重則在特殊圖上跑不出來。只要 vis 數(shù)組存在就一定要在q.push(v)之前把vis[v]置為1而不是等出隊(duì)時(shí)再標(biāo)記。這個(gè)細(xì)節(jié)很多初學(xué)者會(huì)漏。第四個(gè)坑是 check 的提前返回。BFS 一旦遇到目標(biāo)節(jié)點(diǎn)就返回 true這是沒問題的。但要注意如果題目要求輸出完整路徑就不能在發(fā)現(xiàn)目標(biāo)時(shí)直接返回還需要保存前驅(qū)節(jié)點(diǎn)。這道題只問答案值所以簡(jiǎn)化版沒問題。如果你在變式題里遇到輸出路徑的要求千萬別直接搬這段代碼。第五個(gè)坑是優(yōu)先隊(duì)列的小頂堆寫法。Dijkstra變形解法里如果直接寫priority_queuepairint,int pq默認(rèn)是最大堆彈出的永遠(yuǎn)是瓶頸值最大的節(jié)點(diǎn)答案會(huì)完全錯(cuò)誤。必須寫成priority_queuepairint,int, vectorpairint,int, greaterpairint,int pq。這個(gè)greater太容易被忘。第六個(gè)坑是讀入性能。當(dāng) M 達(dá)到 10^5 甚至更高cin默認(rèn)的同步模式會(huì)讓輸入變慢。解決辦法就是ios::sync_with_stdio(false); cin.tie(nullptr);放在 main 函數(shù)最前面。如果這行沒寫某些評(píng)測(cè)機(jī)上會(huì)超時(shí)。4.2 大數(shù)據(jù)范圍下的性能與內(nèi)存這類題的數(shù)據(jù)量在 10^5 附近時(shí)二分BFS的時(shí)間在零點(diǎn)幾秒到一秒出頭之間非常穩(wěn)。BFS每次都要開新的 vis 數(shù)組size為 N110^5級(jí)別的數(shù)組開一次就是一兩百KB二分20次也就幾MB內(nèi)存完全沒問題。并查集解法則更省只需要 parent 數(shù)組和排序后的邊數(shù)組內(nèi)存占用最小。有人說二分BFS比并查集多一個(gè) logW 因子會(huì)不會(huì)更慢實(shí)測(cè)中不會(huì)。因?yàn)?W 即便到 10^9logW 也就30左右每次 BFS 都是 O(NM)總操作量在 3×10^6 量級(jí)現(xiàn)代評(píng)測(cè)機(jī)一兩秒穩(wěn)穩(wěn)跑完。擔(dān)心性能的話優(yōu)先用并查集排序一次然后線性加邊是最少的操作次數(shù)。4.3 考場(chǎng)時(shí)間分配與答題策略雙機(jī)位監(jiān)考的模式下代碼很難反復(fù)調(diào)試所以思路不清晰之前別急著敲鍵盤。我給自己定的規(guī)矩是看到“最小化最大/最大化最小”的題先花三分鐘在草稿紙上確認(rèn)有沒有單調(diào)性確認(rèn)有再開始寫二分答案。如果確認(rèn)不是二分再考慮是不是Dijkstra變形、并查集、BFS狀態(tài)搜索。這道題留25到35分鐘比較合理。前10分鐘用來讀題、建模型、確認(rèn)輸出要求10到20分鐘寫代碼并跑樣例剩下的時(shí)間構(gòu)造邊界數(shù)據(jù)自測(cè)。邊界數(shù)據(jù)至少要包括單節(jié)點(diǎn)圖、兩個(gè)節(jié)點(diǎn)直接相連的圖、不可達(dá)的圖、全圖邊權(quán)相等的圖。每一組都要想清楚預(yù)期輸出是多少再拿程序跑一遍。5. 一些題外話這道題教會(huì)我的東西我自己做這道題最大的收獲不是記住了什么模板而是意識(shí)到機(jī)試真正考察的是“把自然語言翻譯成數(shù)學(xué)模型”的能力。Alice的安全旅行說得再生動(dòng)本質(zhì)就是一張有權(quán)無向圖上的瓶頸最小化問題。一旦完成這個(gè)翻譯接下來選二分還是并查集只是個(gè)人偏好的問題。另外有一點(diǎn)值得提醒做完這道題后可以順手把變式也想一遍。如果題目改成“路徑上邊權(quán)總和最小但路徑長(zhǎng)度不能超過K”那就是分層圖加最短路徑如果改成“必須經(jīng)過若干個(gè)檢查站”那就變成多段最短路的組合問題。機(jī)試題目之間聯(lián)系很緊密吃透一題往往能順帶拿下三五道變種。如果你正準(zhǔn)備這類考試建議把二分答案、并查集、Dijkstra變形這三板斧都練熟遇到類似名字的題目先笑一笑然后冷靜分析它到底考什么模型。做題的心態(tài)穩(wěn)住代碼一遍過的概率就會(huì)高很多。