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