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