最近集中刷了一批圖論最短路題這套 P1567、P2951、P1807、P2419、P4306 的組合很有意思。第一眼看以為全是最短路模板題刷完才發(fā)現(xiàn)它其實覆蓋了從 BFS 到 Dijkstra、從 DAG 最長路到傳遞閉包的一整條線。整理這篇題解一方面是給自己留個備份另一方面是給正在洛谷刷圖論題單的朋友一點參照尤其是那些和我一樣卡在為什么這個題也算最短路的人。如果你剛學完基礎圖論、準備 OI 復賽或者機試這套題的遞進關系非常值得完整走一遍。1. 先摸清這套題單的底細五個題分別對應圖論的哪塊這套題單第一眼看上去挺雜P1567 統(tǒng)計天數(shù)、P2951 捉迷藏、P1807 最長路、P2419 奶牛比賽、P4306 連通數(shù)。五個題五個名字好像誰也不挨著誰。但刷完之后回頭看它們其實是一條線從單源最短路到 DAG 上的最長路從全源可達性到大規(guī)模傳遞閉包優(yōu)化。下面這張表先把這套題的考點擺出來。題號題名核心考點推薦做法P1567統(tǒng)計天數(shù)序列上的最長連續(xù)上升子段單趟掃描嚴格說不是圖論題P2951[USACO09OPEN]捉迷藏邊權為 1 的單源最短路找最遠點BFS堆優(yōu)化 Dijkstra 也能過P1807最長路有向無環(huán)圖DAG上的最長路拓撲排序 DPP2419[USACO08JAN]牛的比賽傳遞閉包判斷關系是否完整Floyd-WarshallP4306[JSOI2010]連通數(shù)大規(guī)模傳遞閉包可達點對數(shù)bitset 優(yōu)化或縮點 DAG DP從遞進關系看P2951 解決的是從一個點出發(fā)到其他點的最短距離這是最短路最原始的形態(tài)。P1807 把最短換成最長但如果圖不是 DAG最長路問題就麻煩得多所以題目特意把圖限制成 DAG好讓拓撲序 DP 成立。P2419 不再關心距離只關心能不能到這就是傳遞閉包可以看成 Floyd 算法在布爾矩陣上的變體。P4306 把點數(shù)拉大到 2000逼著你優(yōu)化 Floyd 的內層循環(huán)。至于 P1567嚴格說它是序列題不屬于圖論。它出現(xiàn)在這個題單里我猜是整理的時候順手放進去的或者是拿來當最長路的入門鋪墊。它跟 P1807 都帶最長兩個字經常有人一起問所以我在第三節(jié)里會專門拿它跟 P1807 做對照。別因為它不是圖論題就跳過序列上的狀態(tài)轉移和圖上的狀態(tài)轉移底層邏輯是相通的。2. P2951 捉迷藏邊權為 1 時的 BFS以及為什么還要會 DijkstraP2951 是 USACO 的經典題。Bessie 要和 John 玩捉迷藏John 從節(jié)點 1 出發(fā)Bessie 要選一個離節(jié)點 1 最遠的節(jié)點躲起來。如果最遠點不止一個選編號最小的一個最后還要輸出最遠節(jié)點的數(shù)量。所有邊的長度都是 1。這個題的本質就是求單源最短路然后在 dist 數(shù)組里找最大值。因為每條邊長度相等BFS 從起點逐層往外擴展節(jié)點第一次被訪問時得到的層數(shù)就是它到起點的最短距離。這個結論是 BFS 正確性的根基隊列里的節(jié)點按距離遞增排列先出隊的距離一定不超過后出隊的所以第一次碰到 v 時dist[v] 就是最終值不需要再被第二次更新。你可以把它理解成水波擴散水面上的波紋是一圈一圈往外走的先到達岸邊的一定是最近的路徑。代碼實現(xiàn)上鄰接表存圖dist 初始化為 -1 表示未訪問起點 1 的距離為 0然后 BFS。搜完之后從頭掃一遍用嚴格大于更新最遠距離和編號用等于且編號更小處理并列最遠點。最后統(tǒng)計所有距離等于最大值的節(jié)點個數(shù)。#include bits/stdc.h using namespace std; const int maxn 20005; vectorint e[maxn]; int dist[maxn]; int main() { int n, m; cin n m; for (int i 0; i m; i) { int a, b; cin a b; e[a].push_back(b); e[b].push_back(a); } memset(dist, -1, sizeof(dist)); queueint q; dist[1] 0; q.push(1); while (!q.empty()) { int u q.front(); q.pop(); for (int v : e[u]) { if (dist[v] ! -1) continue; dist[v] dist[u] 1; q.push(v); } } int ans 1, mx 0, cnt 0; for (int i 1; i n; i) { if (dist[i] mx) { mx dist[i]; ans i; cnt 1; } else if (dist[i] mx dist[i] ! -1) { cnt; if (i ans) ans i; } } cout ans mx cnt endl; return 0; }這里有幾個容易翻車的地方。第一dist 初始化為 -1 而不是 0是為了區(qū)分沒訪問到和距離為 0 的起點。如果題目不保證圖連通那些不可達節(jié)點的 dist 是 -1比較最遠距離時必須排除。第二并列最遠點選編號最小這一步要寫成兩個分支大于才更新編號等于且編號更小才換編號。有人圖省事只寫一個大于號并列情況直接取第一次遇到的點WA 了還不知道錯在哪。第三輸出的是最遠點個數(shù)不是可達點總數(shù)所以用一個 cnt 單獨數(shù)。那學了 BFS 為什么還要學 Dijkstra因為 BFS 的使用條件是邊權全部相等。一旦每條邊的代價不同BFS 的按層擴展就不再代表真實距離這時候才需要 Dijkstra 用優(yōu)先隊列維護當前距離最小的點每次松弛鄰邊。P2951 的數(shù)據(jù)范圍 N 有 20000M 有 50000你直接寫堆優(yōu)化 Dijkstra 也能過但這屬于用牛刀殺雞。做題先看邊權再定算法這個習慣比會背模板重要得多。3. P1807 最長路為什么 DAG 上的最長路要用拓撲排序而不是把 Dijkstra 反過來P1807 給出一個有 n 個點、m 條邊的有向無環(huán)圖每條邊帶一個整數(shù)權值求從節(jié)點 1 到節(jié)點 n 的最長路長度。如果從 1 到不了 n輸出 -1。這里的關鍵詞是有向無環(huán)圖也就是 DAG。只有 DAG 才能高效求最長路。原因有兩點第一沒有環(huán)任何一條路徑都不會無限循環(huán)最長路一定存在并且就是某條簡單路徑第二DAG 存在拓撲序把所有點排成從左到右的序列每條邊都從序列靠前的點指向靠后的點。在這個序列上做 DP每個點的狀態(tài)只依賴左邊的點左邊算完就不會再變這就是無后效性。打個比方拓撲排序就像給圖里的點排隊所有邊都從左往右走右邊點的答案只依賴左邊點的答案好比做菜必須先把菜切好再下鍋順序不能亂。有同學問能不能把 Dijkstra 的求最小改成求最大用最大堆每次取出當前距離最大的點答案是不行。Dijkstra 正確性依賴一個核心假設一旦彈出某個點它的距離就永遠是最終值。對最短路來說任何繞路的路徑只會讓距離變大所以不會再有更小的值但最長路正好相反繞路可能讓距離更大一個點即使被某個路徑更新到了當前最大值后面可能還有一條路徑能讓它變得更大。最大堆彈出的早不代表它的值不會繼續(xù)被更新。SPFA 把松弛方向反過來確實能求最長路但 SPFA 復雜度不穩(wěn)定隨便來個數(shù)據(jù)就能把它卡到退化成 Bellman-Ford。所以 DAG 上的最長路正規(guī)做法是拓撲排序之后 DP。實現(xiàn)流程大概是這樣的建圖同時統(tǒng)計每個點的入度。dist 數(shù)組全部初始化為負無窮dist[1] 0。把所有入度為 0 的點入隊。依次出隊 u遍歷 u 的所有出邊 (u, v, w)如果 dist[u] 不是負無窮就用 dist[u] w 去嘗試更新 dist[v]v 的入度減 1減到 0 就入隊。拓撲排序結束后如果 dist[n] 還是負無窮輸出 -1否則輸出 dist[n]。#include bits/stdc.h using namespace std; const int maxn 1505; const int INF 0x3f3f3f3f; struct Edge { int v, w; }; vectorEdge e[maxn]; int indeg[maxn]; int dist[maxn]; int main() { int n, m; cin n m; for (int i 0; i m; i) { int u, v, w; cin u v w; e[u].push_back({v, w}); indeg[v]; } for (int i 1; i n; i) dist[i] -INF; dist[1] 0; queueint q; for (int i 1; i n; i) if (indeg[i] 0) q.push(i); while (!q.empty()) { int u q.front(); q.pop(); for (auto ed : e[u]) { int v ed.v, w ed.w; if (dist[u] ! -INF) { dist[v] max(dist[v], dist[u] w); } if (--indeg[v] 0) { q.push(v); } } } cout (dist[n] -INF ? -1 : dist[n]) endl; return 0; }這段代碼里最容易漏的是if (dist[u] ! -INF)這個判斷。為什么要判斷因為隊列里所有入度為 0 的點都要進包括從 1 根本到達不了的點。這些點的 dist 是負無窮如果放任它們去更新鄰居負無窮加上邊權還是負無窮看起來好像沒關系但當這個偽負無窮傳給了一個本可以從 1 到達的點就可能覆蓋掉正確的最長路或者讓后續(xù)比較邏輯混亂。判斷一下只讓真正從 1 出發(fā)能到達的點參與松弛問題就干凈了。這里正好可以說說題單里的 P1567。P1567 統(tǒng)計的是最長連續(xù)升溫天數(shù)給你 N 天溫度找最長的連續(xù)上升段。它的解法是從左到右掃一遍如果當天溫度比前一天高當前長度加 1否則重置為 1全程取最大值。這個題跟 P1807 的相似之處在于都是最長都用了狀態(tài)轉移區(qū)別在于 P1567 轉移的方向是數(shù)組下標從左到右P1807 轉移的方向是拓撲序從前到后。理解了這一點你就明白為什么 P1567 這種看似和圖論無關的題也經常被當成最短路和 DAG 動態(tài)規(guī)劃的前置練習。4. P2419 奶牛比賽Floyd 的傳遞閉包用法把勝負關系變成排名P2419 是 [USACO08JAN] 牛的比賽。有 N 頭牛M 場比賽結果每場給出 a b 表示 a 贏了 b。勝負關系有傳遞性如果 a 贏了 bb 贏了 c那么 a 也能贏 c。題目問有多少頭牛的名次可以被唯一確定。把贏了看成有向邊從勝者指向敗者問題就變成了圖的可達性問題。我們用reach[i][j] true表示 i 能夠贏 j也就是從 i 出發(fā)能沿有向邊到達 j。對某頭牛 i 來說如果對于任意另一頭牛 j要么 i 能贏 j要么 j 能贏 i那么 i 和其他所有牛的關系都是確定的i 的名次就能確定。為什么這個條件是充分的排名本質上是有多少頭牛比我強。如果我能確定所有牛里面誰比我強、誰比我弱那么比我強的數(shù)量加 1 就是我的名次。從圖上看能到達 i 的節(jié)點數(shù)量就是比我強的牛數(shù)。關系一旦完整這個數(shù)就唯一反過來只要有一頭牛跟我關系未知它可能排我前面也可能排我后面我的名次就有兩種可能當然確定不了。舉個具體例子1 贏 22 贏 3那么三頭牛的關系都是確定的1 一定排第一2 一定排第二3 一定排第三。但如果我們只知道 1 贏 2不知道 3 和任何人的關系那 3 可能排在最前面也可能排在最后面誰也說不準。所以判定條件可以寫成在傳遞閉包矩陣里第 i 行所有為 true 的個數(shù)加上第 i 列所有為 true 的個數(shù)減去自身那一次重復結果為 N - 1。N 只有 100直接用 Floyd-Warshall 求傳遞閉包。區(qū)別在于普通最短路版存的是距離這里存的是布爾值。#include bits/stdc.h using namespace std; const int maxn 105; bool reach[maxn][maxn]; int main() { int n, m; cin n m; for (int i 0; i m; i) { int a, b; cin a b; reach[a][b] true; } for (int k 1; k n; k) { for (int i 1; i n; i) { if (!reach[i][k]) continue; for (int j 1; j n; j) { reach[i][j] reach[i][j] || reach[k][j]; } } } int ans 0; for (int i 1; i n; i) { int cnt 0; for (int j 1; j n; j) { if (i j) continue; if (reach[i][j] || reach[j][i]) cnt; } if (cnt n - 1) ans; } cout ans endl; return 0; }Floyd 寫的時候要特別注意循環(huán)順序。外層 k 是中間節(jié)點內層 i 和 j 才是被連接的兩端。如果寫成 i、k、j 這種順序或者 i、j、k 的順序很多間接關系會被漏掉因為傳遞性依賴中間節(jié)點已經處理完所有更小中間節(jié)點這一步。這是 Floyd 最容易寫錯、也最難調試的點。另外統(tǒng)計時要把i j的情況排除因為自己和自己的關系不參與排名判定。這里用continue跳過自身比把對角線設成 true 再硬減 1 更直觀也不容易錯。這個題其實也可以用 N 次 BFS 或者 DFS 做對每個點搜一遍統(tǒng)計可達點集再把反向可達用反向圖搜一遍。復雜度 O(NM)N100 時完全能過。但用 Floyd 寫更統(tǒng)一而且下一題 P4306 正好是它的超大規(guī)模版本到時候你就知道 Floyd 的框架怎么改才能活下來。5. P4306 連通數(shù)2000 個點還硬跑 Floyd 會超時bitset 把它救回來P4306 是 [JSOI2010] 連通數(shù)。給一個 n 個點的有向圖n 最大到 2000輸入是一個 n 行 n 列的 01 矩陣第 i 行第 j 列為 1 表示 i 到 j 有邊。題目要求輸出圖中有多少對點 (i, j) 滿足 i 能到達 j其中按連通數(shù)的定義自身到自身也算可達所以答案至少為 n。如果直接套 P2419 的三重循環(huán) Floyd2000 的三次方是 8e9 次操作穩(wěn)穩(wěn)超時。這個題的核心優(yōu)化是 bitset。std::bitset可以把一個長達 2000 的布爾數(shù)組壓進 32 個 64 位整數(shù)里一次按位或就能完成原來需要循環(huán) 2000 次的操作。外層仍然枚舉中間點 k內層枚舉 i如果 i 能到 k就把 k 的整個可達集合按位或到 i 的可達集合上。總復雜度從 O(N^3) 變成大約 O(N^3 / 64)N2000 時大概一億多次位運算是能過的時間范圍。#include bits/stdc.h using namespace std; const int maxn 2005; bitsetmaxn reach[maxn]; int main() { int n; cin n; for (int i 1; i n; i) { string s; cin s; for (int j 0; j n; j) { if (s[j] 1) { reach[i][j 1] true; } } reach[i][i] true; // 連通數(shù)定義自身可達 } for (int k 1; k n; k) { for (int i 1; i n; i) { if (reach[i][k]) { reach[i] | reach[k]; } } } long long ans 0; for (int i 1; i n; i) { ans reach[i].count(); } cout ans endl; return 0; }寫這個題有三個地方值得單說。第一個是輸入格式。圖是以 01 字符串的形式給出的一行一個字符串里面沒有空格。如果按整數(shù)讀讀進來的會是整個字符串的數(shù)值完全不對。正確做法是讀 string再按字符逐位判斷。這一點不仔細看題很容易踩。第二個是自身是否算可達。這個題答案至少是 n因為每個點都能走到自己。如果你把對角線全部初始化成 true最后統(tǒng)計就不會少如果你不初始化答案會少 n直接 WA。有些題目對自身可達的定義不一樣看題優(yōu)先確認不要想當然。第三個是數(shù)據(jù)規(guī)模和類型。2000 個點最多 400 萬個點對int 放得下但我習慣用 long long 統(tǒng)計因為一旦題目升級到 5000、10000int 就會溢出到時候改起來麻煩。除了 bitset 優(yōu)化這個題還有一個更符合圖論本質的思路Tarjan 縮點。先把有向圖縮成若干個強連通分量每個分量內部的點兩兩互通一個大小為 sz 的分量內部貢獻 sz * sz 個點對?？s點之后圖變成 DAG每個分量用一個 bitset 記錄它能到達哪些分量再按拓撲序從后往前合并子節(jié)點的可達集合。具體步驟是第一步 Tarjan 求出所有 SCC第二步用原圖的邊構造縮點后的新圖注意去重第三步在 DAG 上做拓撲 DP每個 SCC 的可達集合初始只包含自己然后把自己的可達集合按位或到所有指向它的前驅上第四步統(tǒng)計答案時每個 SCC 的可達集合里每有一個目標 SCC就要累加當前 SCC 的大小乘目標 SCC 的大小因為一個分量里任何一個點都能到達另一個分量里的任何一個點。這樣做的優(yōu)勢在于點數(shù)到幾萬甚至十萬級別時仍然可能跑得動而純 bitset 的 O(N^3 / 64) 就會吃緊。P4306 用不著這么極限但把這個思想放在腦子里遇到升級版連通數(shù)題就能從容不少。6. 刷完這套題我寫代碼時最在意的四件事這套題單刷下來我對最短路這個板塊的認識比之前完整了不少。以前提到最短路第一反應就是背一個 Dijkstra 模板遇到題就往里套。實際上最短路這套東西是一個完整的工具箱考點分布在不同的圖模型上。第一件在意的事是先看圖再選工具。邊權全等用 BFS正權不等用 DijkstraDAG 用拓撲 DP全源關系用 Floyd 或 bitset。P2951 用 BFS 是最優(yōu)解但如果你只會 Dijkstra 也能過可這不代表你掌握了 BFS 為什么能用。做題不是為了 AC 那一瞬間而是為了建立看到什么條件就想到什么算法的條件反射。第二件在意的事是判斷條件一定是題目的核心。P2419 的判定條件是閉包矩陣里行和列加起來等于 N-1P4306 的判定條件是自身算不算可達。這些細節(jié)不像算法本身那么閃耀但 WA 往往就藏在里面。刷題刷到后面真正拉開差距的不是誰模板背得熟而是誰對題目條件敏感。第三件在意的事是復雜度估算要落到數(shù)據(jù)范圍上。P2419 的 N100Floyd 隨便跑P4306 的 N2000同款代碼就超時。把 N 的約束框出來心里過一遍復雜度很多題在動手之前就知道能不能過。第四件反而是那個混進題單的 P1567 給我的提醒。它告訴我們最長這個詞在不同題目里有完全不同的含義P1567 是數(shù)組上連續(xù)子段的最長P1807 是圖上路徑的最長前者一趟掃描解決后者需要拓撲序保證無后效性。很多入門選手覺得圖論和序列題是兩座山其實它們的動態(tài)規(guī)劃思維完全同源。把序列上的狀態(tài)轉移想通了再去看 DAG 上的 DP會發(fā)現(xiàn)只是把從左到右換成了按拓撲序本質上都是保證每個狀態(tài)只依賴已經計算好的階段。最后再分享一個小習慣每次交這類題之前我都會自己構造一個極端小數(shù)據(jù)走一遍。P2951 就構造一個鏈形圖和一個星形圖P1807 構造一個 1 到不了 n 的圖P4306 構造一個只有自環(huán)的圖。跑通了再交能躲掉很多低級錯誤。這種自測的工夫花不了幾分鐘但回報率比我預想的高得多。