做图论题最怕的就是那种题面看起来像交通规划、实际上一行公式都不给的题目。“DTOJ 4848. 交通网络”就是典型代表光看标题我以为要建什么高精度地图模型结果本质就是判断一个有向图里的关键边。这类题在不少OJ和校赛里都反复出现过换着马甲考同一个套路给你一张有向图找出哪些边一旦被切断就会导致从某个起点出发的可行路径明显变少甚至某些点彻底不可达。这篇文章我会从题目建模开始把“交通网络”这类题背后真正考的图论模型讲透。重点覆盖两种最常见的问法一种是给定起点和终点求所有最短路径上必须经过的边另一种是只给一个起点求删除某条边后会导致某些点不可达的边。这两种模型看似相似判定条件完全不同很多人就是在这里栽跟头。我还会给出完整的判定原理、推导过程和可直接抄走的代码实现适合正在刷图论专题、准备竞赛或者工作中需要做路径可靠性分析的朋友参考。1. 题面分析与问题建模拿到“交通网络”这个标题第一件事不是急着写代码而是把题意翻译成图论语言。1.1 从交通网络到有向图交通网络天然适合建模成图每个路口或城市是节点每条道路是有向边。单向道路、环线、立交桥匝道这些交通场景里的概念放到图论里就是普通有向边、环、以及不能回头的单行线。题目里说“交通网络”大概率给的就是一张有向图然后问某些“关键路段”。关键路段是什么意思直观理解就是如果这条路断了整个网络的通行能力会受影响。具体到图论上通常有两种定义删除某条边后起点无法到达某些原本可达的节点删除某条边后起点到终点的最短路径长度变长。第一种情况对应的是“全局必经边”第二种情况对应的是“最短路必经边”。很多题目会把这两种说法混在一起所以先要搞清楚题面问的是哪一种。如果题面出现了“最短路径”“最短路长度不变”这类词那必然是第二种如果题面只说“不可达”“没法到达”那就是第一种。这两种模型虽然都要判断边的关键性但处理手法差异很大。最短路必经边要先跑两遍最短路然后建DAG全局必经边则要看图的支配结构或路径计数关系。这也是为什么很多人在同一个坑里摔两次——用最短路DAG的解法去解“不可达”题或者反过来结果样例都过不了。1.2 题目中的三个关键点根据我对这类题的拆解无论题面怎么包装核心难点永远是三个第一图的规模一般不小。n和m到10^5甚至2×10^5都是常态。这意味着你不能对每条边都重新跑一遍最短路或者搜索必须想出一个O(nm)或O(m log n)级别的预处理方案然后O(1)判断每条边。第二路径数量是指数级的。直接枚举所有路径判断“是否每条路径都经过某条边”是天文数字必须用数学方法代替枚举。路径计数是这个问题的突破口。第三如何处理“所有路径都经过某条边”这个逻辑。这里其实等价于经过这条边的路径数等于总路径数。只要能把“路径数”算出来问题就变成了一个简单的等式判断。这个转化是整个解题思路的核心。想明白这三点这道题就已经从“无从下手”变成了“套模板”。下面我逐步展开每个环节的原理和实现。2. 核心原理为什么路径计数能判断关键边先看最短路必经边的场景。假设起点是s终点是t我们已经把所有可能出现在最短路径上的边提取出来构成了一张DAG有向无环图。在这张DAG上从s到t可能有几百条、几千条路径问哪些边是每条路径都必须走的。2.1 组合计数里的“必经”判定考虑一条有向边e (u, v)。如果它必经那么从s到t的每一条路径都要经过它。也就是说整条路径可以拆成三段s到u、边(u, v)、v到t。如果从s到u有F[u]种走法从v到t有G[v]种走法那么经过边(u, v)的完整路径数就是F[u] × G[v]。同时从s到t的总路径数是F[t]。那么“所有路径都经过这条边”等价于F[u] × G[v] F[t]这个等式成立说明经过边(u, v)的路径已经覆盖了全部s到t的路径。只要还有任何一条路径绕过这条边等式左边就会小于右边判定立刻失效。这个思路用生活类比来解释就很容易懂。想象一个单向通行的景区所有游客都要从入口s走到出口t。F[u]是到达景点u的游客数量G[v]是从景点v走到出口t的路线数量。如果从u走到v的这条路上的游客数量恰好等于全部游客数量那说明没有游客走其他路线这条路就是必经之路。就是这么朴素的一个道理。2.2 为什么必须用双哈希处理路径数这里有一个非常现实的问题DAG上的路径数会爆炸式增长。一个简单的分层图每层两个节点互相交叉连接路径数就是2的指数次幂。n 60的时候路径数就已经超过10^18long long直接溢出。所以路径计数不能真正存下来必须取模。但只取一个模数有风险。比如用10^97取模两条不同路径数的值可能恰好同余导致误判。虽然这种情况概率不高但在竞赛里一次WA就够难受的。稳妥的做法是选两个大质数模数比如10^97和10^99同时维护两份路径计数。只有当两份计数在各自模数下都满足等式才判定为必经边。两个不同模数下同时发生碰撞的概率极低在实际比赛中用这个方案完全够稳。更讲究一点的做法是用两个随机的64位模数或者在DP转移时用随机权值做哈希。不过对大多数题目来说双质数模数已经够用了代码也简单。2.3 没有固定终点时的判定式现在再看全局必经边的场景。只有起点s没有终点t问题是删除某条边后s是否仍然能到达所有节点。这种情况下不能再用F[t]做分母了因为根本没有唯一的终点。不过可以换个角度思考如果边(u, v)是s到v的必经边意味着所有从s到v的路径最后一步都是从u走到v。也就是说v这个节点只能通过u到达。放到路径计数里就是v的所有可达前驱里只有u一个其他前驱对路径数的贡献都是0。令P[x]表示从s到x的路径数。v的路径数等于所有前驱节点路径数之和P[v] sum(P[p])其中p是v的所有入边起点如果P[u] P[v]而且P[u] 0那就说明所有能到达v的路径其最后一条边都是(u, v)。反过来说如果v还有其他可达的前驱p那么P[p] ≥ 1P[v]就一定会比P[u]大等式不成立。所以全局必经边的判定式是P[u] P[v] 且 P[u] 0这个式子我当初自己想明白的时候有一种“原来如此”的感觉。它本质上是在说v没有任何其他可达的入口所有流量都从u这一条路进来。删除(u, v)后v就彻底失去了来源。3. 实操全流程最短路必经边的完整实现我已经把原理讲清楚了接下来直接上手写代码。这一节以最短路必经边为例因为它是最常见的版本也最能体现从无向图语义到DAG建模的完整流程。3.1 第一步跑两遍Dijkstra要提取最短路DAG必须先知道每个点到起点s的最短距离以及每个点到终点t的最短距离。跑第一遍Dijkstra从s出发得到distS数组。跑第二遍的时候最方便的做法是在反图上从t出发跑一遍得到distT数组。反图就是把每条有向边反向之后的图这样从t出发能到达的点在原图上就是能到达t的点。这里有一个小细节如果原图是带权有向图Dijkstra只适用于边权非负的情况。如果边权可能为负就得换SPFA或其他能处理负权边的算法。交通网络场景下一般默认边权非负但如果题面没说记得检查一下。两遍最短路跑完之后就拿到了两个关键数组。3.2 第二步提取最短路DAG一条边(u, v, w)如果会出现在某条最短路径上必须满足一个条件distS[u] w distT[v] distS[t]这个式子的含义很直观从s出发走到u经过这条边到达v再从v走到t总距离恰好等于s到t的最短距离。满足这个条件的边都保留下来不满足的直接丢弃。保留下来后这些边构成的图有一个非常好的性质它一定是DAG。因为在最短路DAG中每条边(u, v)都满足distS[u] distS[v]。最短路长度沿路径严格递增不可能出现环。这个性质保证了后面做拓扑排序不会卡住。需要特别注意的是重边。如果原图中有多条边连接同一对节点它们的编号不同对应的边权也可能不同。提取DAG时要逐条判断不能合并因为后续输出答案时可能要求输出边的原始编号。3.3 第三步拓扑序DP计数在提取出来的最短路DAG上做动态规划。正向拓扑序遍历计算F数组F[s] 1 对于拓扑序中的每个节点u遍历它在新图中的每条出边(u, v) F[v] F[u]这里F[u]的语义是“从s到u的最短路路径数”。注意只统计最短路DAG中的边因为非最短路边已经被丢掉了。反向拓扑序遍历计算G数组G[t] 1 逆拓扑序中处理每个节点v遍历它的每条入边(u, v) G[u] G[v]G[u]的语义是“从u到t的最短路路径数”。两个数组都算完之后总最短路路径数就是F[t]。判断每条保留边(u, v)是否是必经边时检查F[u] * G[v] F[t]在双哈希版本下就是分别检查两个模数下的等式。这里还要注意一个很多人都会踩的坑如果s本身就无法到达t那F[t] 0所有边的判定都失去意义。此时答案应该是0因为没有任何最短路存在也就不存在必经边。这个特殊判断要写清楚。3.4 完整代码参考下面给出一个可以直接套用的C实现。为了清晰我用了两个模数做双哈希。#include bits/stdc.h using namespace std; typedef long long ll; typedef pairll, int P; const int MAXN 200005; const ll MOD1 1000000007LL; const ll MOD2 1000000009LL; const ll INF 1LL 60; struct Edge { int to, id; ll w; Edge(int _to, int _id, ll _w) : to(_to), id(_id), w(_w) {} }; int n, m, s, t; vectorEdge G[MAXN], RG[MAXN]; vectorint dagG[MAXN], dagRG[MAXN]; // 最短路DAG及其反图 ll distS[MAXN], distT[MAXN]; ll F1[MAXN], F2[MAXN], G1[MAXN], G2[MAXN]; int indeg[MAXN], topo[MAXN], topoCnt; bool onDag[MAXN]; // 边是否在最短路DAG上 void dijkstra(int src, vectorEdge graph[], ll dist[]) { fill(dist, dist n 1, INF); priority_queueP, vectorP, greaterP pq; dist[src] 0; pq.push({0, src}); while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); if (d ! dist[u]) continue; for (auto e : graph[u]) { if (dist[e.to] dist[u] e.w) { dist[e.to] dist[u] e.w; pq.push({dist[e.to], e.to}); } } } } void buildDAG() { for (int u 1; u n; u) { for (auto e : G[u]) { if (distS[u] e.w distT[e.to] distS[t]) { dagG[u].push_back(e.to); dagRG[e.to].push_back(u); indeg[e.to]; } } } } void topoSort() { 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(); topo[topoCnt] u; for (int v : dagG[u]) { if (--indeg[v] 0) q.push(v); } } } void dpForward() { F1[s] F2[s] 1; for (int i 0; i topoCnt; i) { int u topo[i]; for (int v : dagG[u]) { F1[v] (F1[v] F1[u]) % MOD1; F2[v] (F2[v] F2[u]) % MOD2; } } } void dpBackward() { G1[t] G2[t] 1; for (int i topoCnt - 1; i 0; i--) { int v topo[i]; for (int u : dagRG[v]) { G1[u] (G1[u] G1[v]) % MOD1; G2[u] (G2[u] G2[v]) % MOD2; } } } int main() { scanf(%d %d %d %d, n, m, s, t); for (int i 1; i m; i) { int u, v; ll w; scanf(%d %d %lld, u, v, w); G[u].push_back(Edge(v, i, w)); RG[v].push_back(Edge(u, i, w)); } dijkstra(s, G, distS); dijkstra(t, RG, distT); if (distS[t] INF) { printf(0\n); return 0; } buildDAG(); topoSort(); dpForward(); dpBackward(); int ans 0; for (int u 1; u n; u) { for (auto e : G[u]) { if (distS[u] e.w distT[e.to] ! distS[t]) continue; ll ways1 F1[u] * G1[e.to] % MOD1; ll ways2 F2[u] * G2[e.to] % MOD2; if (ways1 F1[t] ways2 F2[t]) { ans; } } } printf(%d\n, ans); return 0; }这段代码里我把边的编号id都存下来了但最终只统计数量。如果题目要求输出具体边的编号在判定成功的地方把e.id加入答案列表即可。还有一点值得提如果F[u]或G[v]为0说明这条边根本不在任何一条s到t路径上但因为我们已经在提取DAG时过滤过一遍正常情况下不会出现。不过为了安全可以在乘法和比较之前加一个判断。4. 全局必经边的判定实现前面讲的是有确定终点t的版本。如果题目问的是“删掉哪些边后源点s无法到达某些点”那就要用P[u] P[v]这套判定。这一节我把这个版本的实现也补全方便对照。4.1 判定式的直观理解再次强调一下P[u] P[v]的含义。在原图可能是普通DAG也可能是缩点后的DAG上从s跑一遍路径计数DP。P[v]是所有能走到v的路径数量之和。因为DP转移是P[v] sum(P[p])p遍历v的所有入边起点所以如果P[v] P[u]而且u是v的前驱之一说明其他所有前驱对P[v]的贡献加起来等于0。换句话说其他前驱节点从s出发都不可达所有能到达v的路径最后一步必然是(u, v)。这在图论里有个很直观的说法v的有效入度是1。这里的“有效”是指从s可达且确实有路径能走到v的前驱。把这个逻辑写成判定条件就是P[u] 0 且 P[u] P[v]4.2 代码片段以普通DAG为例先拓扑排序再做一次正向DP。// 假设原图已经是DAG或者已经通过缩点变成DAG // P1, P2 为双模数路径计数 void countPaths(int s, int n, vectorint dagG[], int indeg[], int topo[], int topoCnt) { P1[s] P2[s] 1; for (int i 0; i topoCnt; i) { int u topo[i]; for (int v : dagG[u]) { P1[v] (P1[v] P1[u]) % MOD1; P2[v] (P2[v] P2[u]) % MOD2; } } } bool isCriticalEdge(int u, int v) { if (P1[u] 0 P2[u] 0) return false; // u不可达边无意义 return P1[u] P1[v] P2[u] P2[v]; }这里要注意如果原图不是DAG而是一张普通有向图不能直接套DP。因为环会导致路径计数无限。此时先用Tarjan强连通分量缩点。缩点后同一个强连通分量内部的边永远不可能是全局必经边——环提供了替代路径删掉环上任意一条边都能绕过去。缩点后只在分量间的DAG上做上述判定。4.3 两种判定式的对比我把两个版本放在一起对比一下方便大家根据题意选择。对比维度最短路必经边全局必经边适用场景给定起点和终点求所有最短路的公共边给定起点删除某边后某点不可达预处理两遍Dijkstra 提取最短路DAG可能需Tarjan缩点 拓扑排序判定等式F[u] * G[v] F[t]P[u] P[v]依赖终点需要终点t不需要终点路径方向最短路DAG中s到t原DAG中s到所有点关键注意点distS[t]为INF时先判退出不可达的边要先剔除很多题目表面上是“交通网络”实际上问的可能是两张图的结合先跑最短路提取DAG再在DAG上做全局必经判定。这种组合题我也见过解法就是把两种方法按顺序拼接起来每一层都用对应的判定式。5. 踩坑记录与常见问题速查这类题写起来不算长但WA点非常多。我把自己实践中踩过的坑和帮别人debug时见过的问题整理一下。5.1 三个高频WA原因第一个坑忘了判distS[t]为INF。如果起点根本到不了终点最短路DAG是空的所有边都不该计入答案。但有些人提取DAG时会写出distS[u] w distT[v] INF的错误等式把所有边都算进来。正确做法是一开始就特判INF直接输出0。第二个坑路径计数没有从s正确初始化。F[s]要初始化为1而不是0。有人会写成默认F数组全是0结果整条链上所有路径计数都是0等式恒成立答案变成所有边。这个错误非常隐蔽因为小规模样例跑出来可能恰好正确。第三个坑单哈希碰撞。路径数量是组合爆炸级别的取模后不同路径数撞同一个余数的概率并不低尤其是数据规模到10^5以上。只用单模数的话一旦碰撞就会误判。解决办法就是老老实实双哈希或者用两个随机64位模数。5.2 重边、负权边和不可达节点重边的情况前面提过这里再强调一下。如果两条边都是从u到v但编号不同、边权也可能不同提取DAG时不能合并。因为最短路条件distS[u] w distT[v] distS[t]里带w两条边权重不同一条可能满足条件另一条可能不满足必须逐条判断。负权边的问题也很致命。Dijkstra遇到负权边会计算出错误结果必须先确认题面保证边权非负。如果题面没保证要么用SPFA要么换算法思路。不过“最短路径”场景下负权边很少见因为负权环会导致最短路不存在。实在不放心的话可以在读入时扫一遍边权。不可达节点对路径计数DP有影响。在全局必经判定版本中如果某个节点从s不可达它的P值是0但它作为前驱时不会破坏P[u] P[v]的等式。这其实是正确的——一个不可达的前驱确实不会提供任何路径。但要注意u本身必须可达否则一条s不可达的边也会因为P[u] P[v] 0而被误判为关键边。所以判定时P[u] 0这个条件不能省。5.3 答案输出方式的决定时机很多同学把算法写完了才发现题目要求输出“关键边的编号”而自己只在判定的地方计数没有保存边号。改起来虽然不难但要重写一遍循环浪费时间。我建议读题之后第一步就确认输出格式是输出关键边数量还是输出关键边编号列表还是输出所有关键边的权值总和。不同输出格式会影响建图时是否要保存边的原始编号、判定时是否要额外记录答案。这个决定最好在写Dijkstra之前就做掉。5.4 一个实用的小优化在判定F[u] * G[v] F[t]时乘法可能溢出long long。虽然在取模之后再乘两个模数下的值都小于10^9乘起来在10^18量级long long勉强能存但为了保险我习惯特判一下F[u]和G[v]都不为0再乘。F[u]为0说明s根本到不了u这条边不在任何s到t路径上G[v]为0说明v到不了t同样不在路径上。这两种情况都可以直接跳过不需要做乘法。这个特判还能顺便避免0乘0导致等式恒真的陷阱。结尾这类“交通网络”题我在不同OJ和校内训练里前前后后写过不下五遍每一次都能踩到一两个新坑。最深的体会是关键边问题的本质不是找边而是数路径。当你被“所有路径”这种字眼吓住的时候记得路径计数就是那个把无限变成有限的钥匙。我个人现在的习惯是拿到图论题先问自己三个问题有没有确定终点图是不是DAG路径数能不能取模比较这三个问题想清楚解法基本就浮出水面了。如果你正在刷图论专题建议把最短路必经边和全局必经边这两道配套题连着做一遍做完之后再自己试试把它们合到一道题里比如先缩点再在缩点后的DAG上找关键边。这种组合练一次比单独刷十道模板题都有用。