图论最短路题单精讲：BFS到Dijkstra、DAG最长路与传递闭包

最近集中刷了一批图论最短路题这套 P1567、P2951、P1807、P2419、P4306 的组合很有意思。第一眼看以为全是最短路模板题刷完才发现它其实覆盖了从 BFS 到 Dijkstra、从 DAG 最长路到传递闭包的一整条线。整理这篇题解一方面是给自己留个备份另一方面是给正在洛谷刷图论题单的朋友一点参照尤其是那些和我一样卡在为什么这个题也算最短路的人。如果你刚学完基础图论、准备 OI 复赛或者机试这套题的递进关系非常值得完整走一遍。1. 先摸清这套题单的底细五个题分别对应图论的哪块这套题单第一眼看上去挺杂P1567 统计天数、P2951 捉迷藏、P1807 最长路、P2419 奶牛比赛、P4306 连通数。五个题五个名字好像谁也不挨着谁。但刷完之后回头看它们其实是一条线从单源最短路到 DAG 上的最长路从全源可达性到大规模传递闭包优化。下面这张表先把这套题的考点摆出来。题号题名核心考点推荐做法P1567统计天数序列上的最长连续上升子段单趟扫描严格说不是图论题P2951[USACO09OPEN]捉迷藏边权为 1 的单源最短路找最远点BFS堆优化 Dijkstra 也能过P1807最长路有向无环图DAG上的最长路拓扑排序 DPP2419[USACO08JAN]牛的比赛传递闭包判断关系是否完整Floyd-WarshallP4306[JSOI2010]连通数大规模传递闭包可达点对数bitset 优化或缩点 DAG DP从递进关系看P2951 解决的是从一个点出发到其他点的最短距离这是最短路最原始的形态。P1807 把最短换成最长但如果图不是 DAG最长路问题就麻烦得多所以题目特意把图限制成 DAG好让拓扑序 DP 成立。P2419 不再关心距离只关心能不能到这就是传递闭包可以看成 Floyd 算法在布尔矩阵上的变体。P4306 把点数拉大到 2000逼着你优化 Floyd 的内层循环。至于 P1567严格说它是序列题不属于图论。它出现在这个题单里我猜是整理的时候顺手放进去的或者是拿来当最长路的入门铺垫。它跟 P1807 都带最长两个字经常有人一起问所以我在第三节里会专门拿它跟 P1807 做对照。别因为它不是图论题就跳过序列上的状态转移和图上的状态转移底层逻辑是相通的。2. P2951 捉迷藏边权为 1 时的 BFS以及为什么还要会 DijkstraP2951 是 USACO 的经典题。Bessie 要和 John 玩捉迷藏John 从节点 1 出发Bessie 要选一个离节点 1 最远的节点躲起来。如果最远点不止一个选编号最小的一个最后还要输出最远节点的数量。所有边的长度都是 1。这个题的本质就是求单源最短路然后在 dist 数组里找最大值。因为每条边长度相等BFS 从起点逐层往外扩展节点第一次被访问时得到的层数就是它到起点的最短距离。这个结论是 BFS 正确性的根基队列里的节点按距离递增排列先出队的距离一定不超过后出队的所以第一次碰到 v 时dist[v] 就是最终值不需要再被第二次更新。你可以把它理解成水波扩散水面上的波纹是一圈一圈往外走的先到达岸边的一定是最近的路径。代码实现上邻接表存图dist 初始化为 -1 表示未访问起点 1 的距离为 0然后 BFS。搜完之后从头扫一遍用严格大于更新最远距离和编号用等于且编号更小处理并列最远点。最后统计所有距离等于最大值的节点个数。#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是为了区分没访问到和距离为 0 的起点。如果题目不保证图连通那些不可达节点的 dist 是 -1比较最远距离时必须排除。第二并列最远点选编号最小这一步要写成两个分支大于才更新编号等于且编号更小才换编号。有人图省事只写一个大于号并列情况直接取第一次遇到的点WA 了还不知道错在哪。第三输出的是最远点个数不是可达点总数所以用一个 cnt 单独数。那学了 BFS 为什么还要学 Dijkstra因为 BFS 的使用条件是边权全部相等。一旦每条边的代价不同BFS 的按层扩展就不再代表真实距离这时候才需要 Dijkstra 用优先队列维护当前距离最小的点每次松弛邻边。P2951 的数据范围 N 有 20000M 有 50000你直接写堆优化 Dijkstra 也能过但这属于用牛刀杀鸡。做题先看边权再定算法这个习惯比会背模板重要得多。3. P1807 最长路为什么 DAG 上的最长路要用拓扑排序而不是把 Dijkstra 反过来P1807 给出一个有 n 个点、m 条边的有向无环图每条边带一个整数权值求从节点 1 到节点 n 的最长路长度。如果从 1 到不了 n输出 -1。这里的关键词是有向无环图也就是 DAG。只有 DAG 才能高效求最长路。原因有两点第一没有环任何一条路径都不会无限循环最长路一定存在并且就是某条简单路径第二DAG 存在拓扑序把所有点排成从左到右的序列每条边都从序列靠前的点指向靠后的点。在这个序列上做 DP每个点的状态只依赖左边的点左边算完就不会再变这就是无后效性。打个比方拓扑排序就像给图里的点排队所有边都从左往右走右边点的答案只依赖左边点的答案好比做菜必须先把菜切好再下锅顺序不能乱。有同学问能不能把 Dijkstra 的求最小改成求最大用最大堆每次取出当前距离最大的点答案是不行。Dijkstra 正确性依赖一个核心假设一旦弹出某个点它的距离就永远是最终值。对最短路来说任何绕路的路径只会让距离变大所以不会再有更小的值但最长路正好相反绕路可能让距离更大一个点即使被某个路径更新到了当前最大值后面可能还有一条路径能让它变得更大。最大堆弹出的早不代表它的值不会继续被更新。SPFA 把松弛方向反过来确实能求最长路但 SPFA 复杂度不稳定随便来个数据就能把它卡到退化成 Bellman-Ford。所以 DAG 上的最长路正规做法是拓扑排序之后 DP。实现流程大概是这样的建图同时统计每个点的入度。dist 数组全部初始化为负无穷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 到达的点就可能覆盖掉正确的最长路或者让后续比较逻辑混乱。判断一下只让真正从 1 出发能到达的点参与松弛问题就干净了。这里正好可以说说题单里的 P1567。P1567 统计的是最长连续升温天数给你 N 天温度找最长的连续上升段。它的解法是从左到右扫一遍如果当天温度比前一天高当前长度加 1否则重置为 1全程取最大值。这个题跟 P1807 的相似之处在于都是最长都用了状态转移区别在于 P1567 转移的方向是数组下标从左到右P1807 转移的方向是拓扑序从前到后。理解了这一点你就明白为什么 P1567 这种看似和图论无关的题也经常被当成最短路和 DAG 动态规划的前置练习。4. P2419 奶牛比赛Floyd 的传递闭包用法把胜负关系变成排名P2419 是 [USACO08JAN] 牛的比赛。有 N 头牛M 场比赛结果每场给出 a b 表示 a 赢了 b。胜负关系有传递性如果 a 赢了 bb 赢了 c那么 a 也能赢 c。题目问有多少头牛的名次可以被唯一确定。把赢了看成有向边从胜者指向败者问题就变成了图的可达性问题。我们用reach[i][j] true表示 i 能够赢 j也就是从 i 出发能沿有向边到达 j。对某头牛 i 来说如果对于任意另一头牛 j要么 i 能赢 j要么 j 能赢 i那么 i 和其他所有牛的关系都是确定的i 的名次就能确定。为什么这个条件是充分的排名本质上是有多少头牛比我强。如果我能确定所有牛里面谁比我强、谁比我弱那么比我强的数量加 1 就是我的名次。从图上看能到达 i 的节点数量就是比我强的牛数。关系一旦完整这个数就唯一反过来只要有一头牛跟我关系未知它可能排我前面也可能排我后面我的名次就有两种可能当然确定不了。举个具体例子1 赢 22 赢 3那么三头牛的关系都是确定的1 一定排第一2 一定排第二3 一定排第三。但如果我们只知道 1 赢 2不知道 3 和任何人的关系那 3 可能排在最前面也可能排在最后面谁也说不准。所以判定条件可以写成在传递闭包矩阵里第 i 行所有为 true 的个数加上第 i 列所有为 true 的个数减去自身那一次重复结果为 N - 1。N 只有 100直接用 Floyd-Warshall 求传递闭包。区别在于普通最短路版存的是距离这里存的是布尔值。#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 写的时候要特别注意循环顺序。外层 k 是中间节点内层 i 和 j 才是被连接的两端。如果写成 i、k、j 这种顺序或者 i、j、k 的顺序很多间接关系会被漏掉因为传递性依赖中间节点已经处理完所有更小中间节点这一步。这是 Floyd 最容易写错、也最难调试的点。另外统计时要把i j的情况排除因为自己和自己的关系不参与排名判定。这里用continue跳过自身比把对角线设成 true 再硬减 1 更直观也不容易错。这个题其实也可以用 N 次 BFS 或者 DFS 做对每个点搜一遍统计可达点集再把反向可达用反向图搜一遍。复杂度 O(NM)N100 时完全能过。但用 Floyd 写更统一而且下一题 P4306 正好是它的超大规模版本到时候你就知道 Floyd 的框架怎么改才能活下来。5. P4306 连通数2000 个点还硬跑 Floyd 会超时bitset 把它救回来P4306 是 [JSOI2010] 连通数。给一个 n 个点的有向图n 最大到 2000输入是一个 n 行 n 列的 01 矩阵第 i 行第 j 列为 1 表示 i 到 j 有边。题目要求输出图中有多少对点 (i, j) 满足 i 能到达 j其中按连通数的定义自身到自身也算可达所以答案至少为 n。如果直接套 P2419 的三重循环 Floyd2000 的三次方是 8e9 次操作稳稳超时。这个题的核心优化是 bitset。std::bitset可以把一个长达 2000 的布尔数组压进 32 个 64 位整数里一次按位或就能完成原来需要循环 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; // 连通数定义自身可达 } 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 字符串的形式给出的一行一个字符串里面没有空格。如果按整数读读进来的会是整个字符串的数值完全不对。正确做法是读 string再按字符逐位判断。这一点不仔细看题很容易踩。第二个是自身是否算可达。这个题答案至少是 n因为每个点都能走到自己。如果你把对角线全部初始化成 true最后统计就不会少如果你不初始化答案会少 n直接 WA。有些题目对自身可达的定义不一样看题优先确认不要想当然。第三个是数据规模和类型。2000 个点最多 400 万个点对int 放得下但我习惯用 long long 统计因为一旦题目升级到 5000、10000int 就会溢出到时候改起来麻烦。除了 bitset 优化这个题还有一个更符合图论本质的思路Tarjan 缩点。先把有向图缩成若干个强连通分量每个分量内部的点两两互通一个大小为 sz 的分量内部贡献 sz * sz 个点对。缩点之后图变成 DAG每个分量用一个 bitset 记录它能到达哪些分量再按拓扑序从后往前合并子节点的可达集合。具体步骤是第一步 Tarjan 求出所有 SCC第二步用原图的边构造缩点后的新图注意去重第三步在 DAG 上做拓扑 DP每个 SCC 的可达集合初始只包含自己然后把自己的可达集合按位或到所有指向它的前驱上第四步统计答案时每个 SCC 的可达集合里每有一个目标 SCC就要累加当前 SCC 的大小乘目标 SCC 的大小因为一个分量里任何一个点都能到达另一个分量里的任何一个点。这样做的优势在于点数到几万甚至十万级别时仍然可能跑得动而纯 bitset 的 O(N^3 / 64) 就会吃紧。P4306 用不着这么极限但把这个思想放在脑子里遇到升级版连通数题就能从容不少。6. 刷完这套题我写代码时最在意的四件事这套题单刷下来我对最短路这个板块的认识比之前完整了不少。以前提到最短路第一反应就是背一个 Dijkstra 模板遇到题就往里套。实际上最短路这套东西是一个完整的工具箱考点分布在不同的图模型上。第一件在意的事是先看图再选工具。边权全等用 BFS正权不等用 DijkstraDAG 用拓扑 DP全源关系用 Floyd 或 bitset。P2951 用 BFS 是最优解但如果你只会 Dijkstra 也能过可这不代表你掌握了 BFS 为什么能用。做题不是为了 AC 那一瞬间而是为了建立看到什么条件就想到什么算法的条件反射。第二件在意的事是判断条件一定是题目的核心。P2419 的判定条件是闭包矩阵里行和列加起来等于 N-1P4306 的判定条件是自身算不算可达。这些细节不像算法本身那么闪耀但 WA 往往就藏在里面。刷题刷到后面真正拉开差距的不是谁模板背得熟而是谁对题目条件敏感。第三件在意的事是复杂度估算要落到数据范围上。P2419 的 N100Floyd 随便跑P4306 的 N2000同款代码就超时。把 N 的约束框出来心里过一遍复杂度很多题在动手之前就知道能不能过。第四件反而是那个混进题单的 P1567 给我的提醒。它告诉我们最长这个词在不同题目里有完全不同的含义P1567 是数组上连续子段的最长P1807 是图上路径的最长前者一趟扫描解决后者需要拓扑序保证无后效性。很多入门选手觉得图论和序列题是两座山其实它们的动态规划思维完全同源。把序列上的状态转移想通了再去看 DAG 上的 DP会发现只是把从左到右换成了按拓扑序本质上都是保证每个状态只依赖已经计算好的阶段。最后再分享一个小习惯每次交这类题之前我都会自己构造一个极端小数据走一遍。P2951 就构造一个链形图和一个星形图P1807 构造一个 1 到不了 n 的图P4306 构造一个只有自环的图。跑通了再交能躲掉很多低级错误。这种自测的工夫花不了几分钟但回报率比我预想的高得多。