图算法的前一段线索是遍历与最短路:它们回答"能否到达"以及"以最小代价到达"。这一答案是局部的——要么针对一个顶点,要么针对一条路径。另有一类问题关心的是整体:一张有向图能否被划分为若干"内部互相可达"的部分,一个容量受限的网络最多能输送多少,两组对象最多能配成多少对。这些问题的解是一个集合或一个数值,而不是一条路径,其算法也不再基于单次搜索的推进,而基于"存在性定理 + 增量改进"的结构:由定理刻画最优解的判别条件(无增广路、无更小容量的割),再由算法反复消除违反条件的结构。本文承接 抽象数据类型(ADT) 中"逻辑结构与存储结构分离"的口径与 复杂度与算法分析 中复杂度的比较方法,按"起源—原理—实现—总结"展开。
一、起源:三类由关系方向与资源上限引出的问题
1.1 可达关系的不对称性与强连通划分
无向图中的可达关系是对称的:若从 u 能走到 v,则从 v 也能走回 u;因此连通分量把顶点划分成互不相交的组,这一划分由一次遍历即可给出;若边是按时间增量加入的,同一划分可以用并查集维护,见 线段树与并查集。
有向图中这一对称性不再成立。从 u 到 v 有路径,不意味着从 v 到 u 有路径。可达关系本身仍具有自反性与传递性,缺少的是对称性,因此它不构成等价关系,无法直接给出划分。为了让划分成立,需要在可达关系上再叠加一层条件:
| 概念 | 定义 | 是否给出划分 |
|---|---|---|
| 可达 | 存在 u 到 v 的有向路径 | 否 |
| 弱连通 | 把有向边视为无向边后连通 | 是,但丢失方向信息 |
| 单向可达 | 从 u 可达 v,或从 v 可达 u | 否 |
| 强连通 | u 可达 v 且 v 可达 u | 是(强连通是等价关系) |
强连通关系满足自反(长度为 0 的路径)、对称(定义本身)、传递(两条路径可拼接)三条性质,因而可以对顶点集合作出唯一的划分。每个划分块称为强连通分量(Strongly Connected Component,SCC),块之间的可达关系则是单向的。
这一划分的实际需求来自依赖关系。模块、包、类、任务之间的依赖构成有向图:A 依赖 B 意味着 A 需要 B 先就绪。若一组对象互相依赖,它们之间无法排出先后顺序,必须作为一个整体处理;若整个图中不存在这样的组,依赖关系就退化为一个偏序,可以按拓扑序逐层处理。因此需要回答两个问题:图中哪些顶点构成不可分割的整体;去掉这些整体后,剩余部分能否排出顺序。
1.2 容量受限下的最大输送
第二类问题的形态是:一张有向图,每条边有容量上限(可承载的流量、带宽、货物量),指定源与汇,问从源到汇最多能输送多少,以及如何分配。
与最短路问题的区别在于解的形态。最短路求的是一条路径,其代价是可加的;最大输送求的是一组流量分配,其约束分为两类:每条边上的量不超过容量,每个中间节点上进出的量相等(既不产生也不消耗)。目标的单一数值(总输送量)不依赖于任何单条路径的走向。
这类结构在工程中反复出现:
- 带宽与流量:链路的物理带宽作为容量,节点设备作为中间顶点,可承载的并发流量有上限。
- 供需与调配:供应方的可供量、需求方的需求量、运输通道的通过能力,三者共同决定最多能满足多少需求。
- 工序与并行度:任务的处理能力、阶段之间的等待队列容量、下游消费速率。
- 资源分配:预算、机时、配额作为可分割的资源,在多个使用方之间分配。
该问题的一个重要性质是它与另一类问题等价:把顶点划分为两个集合(源在其中一侧、汇在另一侧)的"割"存在一个容量,且最小割的容量恰等于最大流量。这使"最多能输送多少"与"瓶颈在哪里"变成同一个问题的两面。
1.3 两类独立集合的配对问题
第三类问题的形态是两组对象之间的配对:任务与人员、商品与仓库、请求与服务实例、学生与志愿。边表示"可以配对",要求每个对象最多出现在一个配对中(一个任务只由一个人做,一个人只做一个任务),问最多能配成多少对,或在一定收益下如何配对总收益最大。
与网络流的区别在约束的位置:网络流的约束在边上(通过量不超过容量),配对问题的约束在顶点上(每个对象只能用一次)。这一差异使配对问题有专门的算法,也使它的一个特例恰好可以用单位容量的网络流表达。
配对问题还牵出一组相关量。点覆盖(用最少顶点覆盖全部边)、独立集(互不相邻的最大顶点集合)与匹配在一般图上是三个难度不同的问题,而在两类对象之间没有"同组内的边"的图上,三者由一条定理联系起来,可以互相换算。
二、原理
三类问题共用一个前提:图是逻辑结构,它的存储方式(邻接矩阵、邻接表、边数组)与算法可以分离,这与 抽象数据类型(ADT) 中"逻辑结构与存储结构分离"的口径一致。以下按"结构 → 判别条件 → 算法"的顺序展开。
2.1 强连通分量
2.1.1 可达与强连通的定义
设 G = (V, E) 为有向图。
- 路径:顶点序列 v₀, v₁, …, v_k,其中每条 (v_i, v_{i+1}) ∈ E。长度为 0 的路径只有一个顶点。
- 可达:存在 u 到 v 的路径,记作 u → v。
- 强连通:u → v 且 v → u。
- 强连通分量:一个极大强连通子集,即该子集内任意两点强连通,且不能再加入任何其他顶点而保持这一性质。
三条基本性质:
- 划分性:任意两个强连通分量不相交。若两个分量有公共顶点,则该顶点与两个分量中的任意点互相可达,两个分量应合并,与极大性矛盾。
- 缩点无环:把每个分量视为一个顶点,分量之间的边(只要存在 u∈C₁、v∈C₂ 且 (u,v)∈E)构成的图是 DAG。若该图有环,则环上的分量互相可达,同样应合并。
- 单向可达:缩点图中任意两点之间的路径是单向的,因此缩点图可以拓扑排序。
这两条性质决定了强连通分量的用途:它把有向图化简为 DAG 上的顺序问题,而顺序问题已知有多种线性或多项式解法。
2.1.2 Kosaraju:两次 DFS 与完成序
Kosaraju 的思路是两次深度优先搜索:
输入:有向图 G
1. 在 G 上做 DFS,按顶点完成(其全部出边处理完毕)的先后记录完成序 finish[]
2. 构造反向图 G^R(把每条边反向)
3. 按 finish 从大到小的顺序,在 G^R 上做 DFS
每一次 DFS 访问到的顶点集合就是一个强连通分量
正确性依赖两条观察:
- 完成时间最晚的顶点属于缩点图的源分量(在缩点图中没有入边的分量)。若它到其他分量有边,则该分量的所有顶点都会先于它完成,与"完成最晚"矛盾。
- 在反向图上从源分量出发,只能到达该分量自身的顶点。缩点图中源分量没有入边,因此反向图中它没有出边,无法离开自身。
第二条观察解释了为什么第二步要按完成序递减的顺序进行:每次都在反向图中从当前"最靠前"的分量出发,搜索会被限制在该分量内,搜索树的顶点集合即为一个分量。完成序的递减顺序相当于缩点图的拓扑序(源在前)。
复杂度 O(V+E):两次 DFS 各遍历一次全部顶点与边。空间上除邻接表外需要保存反向图(约两倍边数)与完成序数组。
2.1.3 Tarjan:时间戳、栈与 lowlink
Tarjan 用一次 DFS 完成同样的划分,代价是需要维护三个量:
- dfn[u]:顶点 u 被首次访问的次序(时间戳)。
- low[u]:u 及其在 DFS 树中的后代,经过至多一条非树边(回边,指向栈中的顶点)所能到达的最小 dfn。
- 栈与在栈标记:保存"已访问但所属分量尚未确定"的顶点。
更新规则(沿 u 的出边 (u,v)):
| v 的状态 | 边的类型 | 更新 |
|---|---|---|
| 未访问 | 树边 | 先递归处理 v,之后 low[u] = min(low[u], low[v]) |
| 已访问且在栈中 | 回边或横叉边 | low[u] = min(low[u], dfn[v]) |
| 已访问且不在栈中 | 指向已完成分量 | 不更新 |
出栈条件:当 u 的全部出边处理完毕,若 dfn[u] == low[u],则 u 所在分量中所有顶点的 low 都不小于 dfn[u],它们无法回溯到栈中更早的顶点,因此栈中从 u 到栈顶的顶点构成一个强连通分量,把它们依次弹出并赋予同一分量编号。
两条容易混淆的规则:
- 已访问且在栈中时用 dfn[v],而不是 low[v]。用 low[v] 会把 u 的 low 拉到 v 所回溯到的更早顶点上,而 v 可能属于另一个尚未完成的分量,导致两个分量被错误合并。
- 已访问且不在栈中的顶点必须忽略。这类顶点属于已完成的分量,其边是横叉边,不能作为回溯依据。若把"已访问"与"在栈中"两个条件合并成
dfn[v] != 0,就会在这里出错。
Tarjan 与 Kosaraju 的复杂度同为 O(V+E)。两者的取舍:
| 维度 | Kosaraju | Tarjan |
|---|---|---|
| DFS 次数 | 两次 | 一次 |
| 额外空间 | 邻接表 + 反向图 + 完成序 | 邻接表 + dfn/low/栈 |
| 实现难度 | 低(无需理解 lowlink 的更新细节) | 中(三条更新规则与出栈判定必须准确) |
| 分量编号顺序 | 按缩点图的拓扑序 | 按缩点图的逆拓扑序(汇分量先出栈) |
| 适用 | 顶点的访问顺序无关,容易验证 | 需要在一次 DFS 内完成(如与其它过程合并) |
分量编号顺序这一差别在 2-SAT 的赋值构造中会直接影响结果的正确性,实现时必须固定约定并测试。
2.1.4 缩点后的有向无环图及其用途
把每个分量缩为一个顶点后,得到 DAG,称为缩点图(condensation)。用途集中在四类:
- 循环依赖检测。存在大小大于 1 的分量,或存在自环,则原图中存在有向环。相比"DFS 找环",强连通分量的优势是给出同一环上的全部成员——修复循环依赖需要完整成员集合,而 DFS 通常只报出找到的第一个环。
- 顺序与分层。对缩点图做拓扑排序,得到的层序是合法的执行顺序;同一分量内的成员必须整体处理。构建系统的模块编译顺序、任务流水线的阶段划分都属于这一类。拓扑排序的两种实现(Kahn 入度法与 DFS 完成序法)、环检测与具体回路的定位见 图的表示与遍历。
- DAG 上的最优化。缩点后可以按拓扑序做动态规划:最长路径、路径计数、可行性传播等。原图上的这类问题因环的存在无法直接定义,缩点把问题转化为可解形态。
- 问题化简。若同一分量内的顶点在某问题上必须同取同舍,则可以把整个分量作为单个决策单元,从而压缩问题规模。
2.2 2-SAT
问题定义。给定 n 个布尔变量 x₁…x_n 与 m 个约束,每个约束形如 (a ∨ b),其中 a、b 是某个变量或其否定(称为文字)。判断是否存在一组赋值使全部约束为真。字句长度为 2 的合取范式可满足性问题称为 2-SAT。
问题难度的分界。字句长度从 2 增加到 3,问题从多项式可解跳到 NP-complete。这一分界使 2-SAT 具有实用价值:一类看似复杂的约束求解问题,只要每个约束只涉及两个文字,就能在线性时间内判定。
蕴涵图的构造。字句 (a ∨ b) 等价于两个蕴涵:
a ∨ b ≡ (¬a → b) ∧ (¬b → a)
为每个文字(x 与 ¬x)建立一个顶点,共 2n 个顶点。每个字句加入两条有向边。在蕴涵图中,一条路径 a → b 的含义是"若 a 为真,则 b 必须为真",这是赋值必须满足的传递约束。
可满足性判定。判定条件是一条简洁的等价关系:
2-SAT 可满足 ⟺ 对每个变量 x,x 与 ¬x 不在同一个强连通分量中
理由是两个方向:
- 若 x 与 ¬x 互相可达(同一分量),则同时存在 x → ¬x 与 ¬x → x 的路径,即"x 为真则 x 为假"与"x 为假则 x 为真"必须同时成立,任何赋值都矛盾。
- 若对每个变量两者都不同分量,则以下构造方式给出合法的赋值:在缩点图上按拓扑序从后往前处理,遇到尚未赋值的分量,就把该分量内所有文字置为真;由于 x 与 ¬x 所在的分量之间只有单向可达关系,先被处理的(拓扑序靠后的)那个分量取真不会与其否定所在分量产生冲突。
取值构造方法。上面的构造规则可以省去显式的拓扑排序:Tarjan 求出的分量编号恰是缩点图的逆拓扑序(编号从 0 递增,对应从汇端到源端),因此可以按编号从小到大处理,取 comp[x] 与 comp[¬x] 中编号较小者对应的文字为真。使用 Kosaraju 时编号顺序相反,规则改为取编号较大者。两种约定对应的结论不同,写错会导致"判定为可满足但构造出的赋值不满足约束",因此实现时应固定一种编号约定,并用小规模随机实例与穷举对照验证。
复杂度 O(n + m):蕴涵图有 2n 个顶点、2m 条边,一次强连通分量求解即可。
2.3 网络流基础
2.3.1 流网络与流
流网络 G = (V, E) 是一个有向图,每条边 (u,v) 有非负容量 c(u,v) ≥ 0,指定两个特殊顶点:源 s 与汇 t,其余顶点称为中间顶点。为使形式统一,约定不存在边的两点之间容量为 0。
流 f 是定义在顶点对上的实函数,满足三条:
| 条件 | 表达式 | 含义 |
|---|---|---|
| 容量约束 | 0 ≤ f(u,v) ≤ c(u,v) | 每条边的流量不超过容量 |
| 反对称 | f(u,v) = −f(v,u) | 反向流量视为负流量,便于统一处理残量 |
| 流量守恒 | 对中间顶点 u,Σ f(v,u) = Σ f(u,w) | 中间顶点不产生也不消耗流量 |
流的值定义为源点的净流出:
|f| = Σ_v f(s, v) − Σ_v f(v, s)
反对称与守恒共同保证:源点的净流出等于汇点的净流入。容量约束与守恒是两类不同的约束,前者作用在边上("最多通过多少"),后者作用在顶点上("进来多少出去多少"),这一区分在建模时决定了约束应该写在何处。
2.3.2 残量网络与增广路
残量网络 G_f 与原图同顶点,边上的残量定义为:
c_f(u, v) = c(u, v) − f(u, v) 容量中尚未使用的部分
约定残量非负,因此原图与反向边都可能出现在残量网络中:
- 若 f(u,v) < c(u,v),则残量网络中有一条 u → v 的边,残量为 c(u,v) − f(u,v),表示还可以继续推送的量。
- 若 f(u,v) > 0,则残量网络中有一条 v → u 的边,残量为 f(u,v),表示可以撤销已有的流量。
反向边的意义是"撤销与改道"。它使算法在发现既有分配不优时可以退回,这一机制是网络流算法能够达到最优的根本原因,也是实现中最容易遗漏的部分。
增广路是残量网络中从 s 到 t 的一条简单路径。沿该路径把每条边的流量增加 d = min c_f(路径上的瓶颈残量),得到的新流仍是合法流,且流值增加 d。由于增广同时增加反向边的残量,后续步骤可以撤销本次推送。
关键引理:
- 沿增广路增广后得到合法流,流值增加 d。
- f 是最大流 ⟺ 残量网络 G_f 中不存在 s 到 t 的路径。(若存在增广路则流不是最大;若不存在,则由 s 可达顶点集构造的割证明 f 已是最大流。)
- 整数性:若所有容量为整数,则每次增广的瓶颈 d 为整数,最大流存在整数解。这使流模型可以表达"最多几个任务""最多几份配额"这类离散语义,无需额外的整数约束。
2.3.3 割与最大流最小割定理
割 (S, T) 是顶点集的一个划分:s ∈ S,t ∈ T,T = V − S。割的容量定义为只计 S 到 T 方向的边:
c(S, T) = Σ_{u∈S} Σ_{v∈T} c(u, v)
注意 T 到 S 的边不计入容量。这是有向图割容量不对称的根源,也是"最小割"在有向图上与无向图不同的地方。
两条性质:
- 弱对偶:对任意流 f 与任意割 (S,T),有 |f| ≤ c(S,T)。证明方式是把流量守恒式对 S 中所有中间顶点求和,得到 |f| = Σ_{u∈S,v∈T} f(u,v) ≤ Σ_{u∈S,v∈T} c(u,v)。因此任何割的容量都是流值的上界。
- 构造性:取 S 为残量网络中从 s 可达的顶点集,则所有从 S 到 T 的边都饱和(残量为 0),所有从 T 到 S 的边流量为 0,于是 |f| = c(S,T)。这给出了由最大流构造最小割的直接方法。
最大流最小割定理:
max |f| = min c(S, T)
以下三个命题等价:f 是最大流;G_f 中不存在增广路;存在割 (S,T) 使 |f| = c(S,T)。
含义与直觉。定理把一类优化问题(输送量最大)与一类划分问题(割容量最小)等价起来。其工程含义是双重的:最大流的值给出系统的输送上限;最小割给出瓶颈集合——只有在瓶颈集合上扩容才能提升上限,在非瓶颈的边上增加容量没有收益。这使"瓶颈定位"从经验判断变为可计算的结果。
2.4 最大流算法
2.4.1 Ford-Fulkerson 框架与复杂度缺陷
Ford-Fulkerson 是一个框架而非具体算法:只要残量网络中存在增广路,就沿任意一条增广路增广,直到不存在增广路。
初始化所有边的流量为 0
while 残量网络中存在 s 到 t 的路径 P:
d = min{ c_f(u, v) | (u, v) ∈ P }
沿 P 把每条边的流量增加 d
返回当前流
复杂度为 O(E·|f|):每次增广至少使流值增加 1(整数容量下),增广次数不超过 |f|,每次找路径与更新代价 O(E)。这一结论暴露了框架的缺陷——复杂度取决于最大流的值,而不是取决于图的规模:
- 容量为大整数时不可用。若图中存在一条容量为 10¹² 的路径与一个容量为 1 的瓶颈,某些选路策略会每次只推送 1 个单位,增广次数达到 10¹²。
- 容量以二进制编码时,|f| 相对输入长度是指数级的。因此 O(E·|f|) 不是输入规模的多项式。
- 无理数容量时不保证终止。用 DFS 选路可能构造出收敛的增广序列,使算法永不结束。
结论:Ford-Fulkerson 只确定了"增广路 + 残量网络"这一正确性框架,实际算法必须对选路方式施加约束以消除对容量值的依赖。
2.4.2 Edmonds-Karp:BFS 选路
把选路方式固定为 BFS(每次选边数最少的增广路),得到 Edmonds-Karp 算法。复杂度降为 O(V·E²),与容量值无关。
正确性依据两条:
- 最短增广路的长度单调不减。增广可能使某些边饱和,但不会产生更短的 s-t 路径;若产生了更短的路径,则该路径在增广前就已存在(因为增广只减少正向残量、增加反向残量,而反向边构成的路径长度不小于原路径长度)。
- 每条边成为瓶颈(饱和)的次数受限。某条边 (u,v) 饱和后,需等到它再次出现在更短的路径上才可能被再次增广,而这要求最短路径长度增加至少一次。最短路径长度从 1 最多增加到 V,因此每条边最多饱和 O(V) 次,总增广次数为 O(V·E)。每次增广的 BFS 与更新代价为 O(E),合计 O(V·E²)。
该算法的价值在于实现简单(一次 BFS 加一次回溯)且复杂度不依赖容量值。适用规模为数百个顶点;顶点数达到数千时 O(V·E²) 会明显受限。
2.4.3 Dinic:分层图与当前弧优化
Dinic 用两步把增广的"批量性"提升上来:
第一步,分层。在残量网络上 BFS,得到每个顶点到 s 的最短边数 level[v]。若 t 不可达,算法结束。
第二步,阻塞流。只保留满足 level[v] = level[u] + 1 的边(称分层图),在其上用 DFS 反复寻找增广路,直到分层图中不存在 s 到 t 的路径。此时得到的是分层图的一个阻塞流(blocking flow):每条 s-t 路径上至少有一条边已饱和。
第三步,重复。增广后残量网络发生变化,可能有更短的路径出现,因此必须重新 BFS 分层,再次求阻塞流。这一循环的终止条件是 t 在残量网络中不可达。
复杂度分析的三段:
- 轮数不超过 V。每次重新分层后,最短增广路的长度严格增加(阻塞流使当前所有最短路径被破坏,下一轮的最短路径只能更长)。最短路径长度取值在 1 到 V−1 之间,因此最多 O(V) 轮。
- 单轮阻塞流的代价。若不加优化,DFS 会反复从表头扫描已无增广空间的边,单轮代价可达 O(V·E)。
- 当前弧优化。为每个顶点维护"下一个待尝试的边"下标 iter[u]。当一条边被确认无法增广(其残量为 0,或其后继顶点在本轮分层中已无法到达 t),就把 iter[u] 前移。于是每条边在单轮中最多被尝试常数次,单轮代价降为 O(V·E)。
合计复杂度 O(V²E)。三个特例的界明显更好:
| 输入类型 | 复杂度 | 说明 |
|---|---|---|
| 一般图 | O(V²E) | 通用界 |
| 单位容量网络 | O(E·min(V^{2/3}, √E)) | 每条边容量为 1 |
| 二分图匹配(源汇边容量为 1) | O(E·√V) | 匹配问题的专用界 |
复杂度对照:
| 算法 | 选路方式 | 复杂度 | 依赖容量值 | 适用规模 |
|---|---|---|---|---|
| Ford-Fulkerson(DFS 选路) | 任意 | O(E·|f|) | 是 | 仅理论参照 |
| Edmonds-Karp | BFS 最短增广路 | O(V·E²) | 否 | V 在数百以内 |
| Dinic | 分层图 + 阻塞流 + 当前弧 | O(V²E) | 否 | V 在 10³ 至 10⁴,通用首选 |
| Dinic(单位容量) | 同上 | O(E·min(V^{2/3}, √E)) | 否 | 边长容量为 1 |
| Dinic(二分图匹配) | 同上 | O(E·√V) | 否 | 匹配模型 |
存在若干进一步优化的算法(如 ISAP、预流推进 HLPP,后者在部分图上可达 O(V²√E)),但实现复杂度显著上升。工程实践中,Dinic 加当前弧优化是在实现代价与性能之间的常见折中。
2.5 费用流
2.5.1 引入单位费用后的目标
容量刻画的是"最多多少",而许多问题还需要表达"以什么代价"。例如同样满足最大输送量,希望总运费最低;同样完成全部任务,希望总成本最小;同样配对,希望总收益最大。为此在每条边上增加单位费用 w(u,v),得到带费用的流网络。
最小费用最大流的目标是:在所有最大流中,使总费用
cost(f) = Σ_{(u,v)∈E} f(u,v) · w(u,v)
最小。两个变体:给定流量值 F 时使费用最小(最小费用流),以及流量最大的同时费用最小(最小费用最大流,可视为前者的一个特例)。
残量网络的费用:正向边保留费用 w,反向边费用取 −w。含义是撤销一个单位的流量时,退回该单位已付出的费用。这与容量上的处理是对称的:正向边残量增加表示可以继续推送,反向边残量增加表示可以撤销。
2.5.2 连续最短路增广
连续最短路增广(Successive Shortest Paths,SSP)的思路与最大流的增广路框架同构,只是把"任意路径"换成"费用最小的路径":
初始化所有边的流量为 0,总费用为 0
while 残量网络中存在 s 到 t 的路径:
在以费用为权的残量网络上求一条 s 到 t 的最短路 P
d = min{ c_f(u, v) | (u, v) ∈ P }
沿 P 推送 d,更新残量与总费用
返回当前流与总费用
正确性依据:若初始残量网络中没有负环,每次沿最短路增广后残量网络仍然没有负环。因此算法每个阶段得到的流都是"该流量下的最小费用流",最终流量达到最大流时即为最小费用最大流。
负环与无界。若残量网络中存在从 s 可达、且边上残量全为正的负费用环,可以沿该环反复循环推送:流量值不变(环上净流出为 0),费用不断下降,因此问题没有有限最优解。这类结构必须在建模阶段消除,例如把环上某条边的费用下界调整为 0,或把它表达为显式约束。
2.5.3 SPFA 与势函数(Johnson 技巧)处理负权
困难来自反向边:它的费用为负,而求最短路的标准算法 Dijkstra 要求非负权。两条解决路径:
路径一:SPFA(Bellman-Ford 的队列实现)。直接处理负权,每轮最短路 O(V·E),增广次数与流量值相关,总复杂度 O(F·V·E)。实现最短,是费用流的常用写法。SPFA 的最坏复杂度较差(与入队次数相关),在费用分布单一时可能明显偏慢。
路径二:势函数。为每个顶点维护一个势 h[v],把边权改写为
w'(u, v) = w(u, v) + h[u] − h[v] 称为 reduced cost
若 h[v] 恰好是上一轮残量网络中 s 到 v 的最短距离,则所有残量边满足 w' ≥ 0(三角不等式),Dijkstra 可用。每轮 Dijkstra 求出以 w' 为权的最短路 dist[] 后,用 h[v] += dist[v] 更新势,新的残量边(本轮增广路径上的反向边)在更新后的势下 reduced cost 为 0,非负性得以保持。
初始:若存在负费用边,先用 SPFA/Bellman-Ford 求一次 s 到各点的最短距离作为 h[]
若所有费用非负,取 h[] ≡ 0
每轮:
1. 以 w'(u, v) = w(u, v) + h[u] − h[v] 为权,用 Dijkstra 求 dist[]
2. 若 t 不可达,算法结束
3. 本轮真实最短路费用 = dist[t] + h[t] − h[s](用更新前的 h)
4. 沿前驱数组回溯,增广瓶颈流量,累加"真实费用 × 瓶颈"
5. 对 dist[v] 有限的顶点执行 h[v] += dist[v]
复杂度为 O(F·E·log V):每轮 Dijkstra 的代价为 O(E log V)(用二叉堆时为 O(E log V),参见 堆与优先队列 中图算法与优先队列一节),增广次数与 SPFA 版本相同。
第 3 步与第 5 步的关系值得注意:若把第 5 步放在第 3 步之前,则更新后有 h_new[t] = h_old[t] + dist[t],同一式可写成 h_new[t] − h_new[s],两种写法一致,但不可混用同一轮的新旧势。实现时应固定一种顺序。负权与负环的最短路处理方式(Bellman-Ford、SPFA 与 Johnson 重标号)见 最短路径与最小生成树。
2.6 二分图匹配
2.6.1 匹配与相关定义
二分图 G = (X, Y, E):顶点集划分为 X 与 Y,每条边的两个端点分属两侧(X 内部与 Y 内部无边)。等价的判定条件是图中不存在长度为奇数的环。
匹配 M ⊆ E 是一个边集合,其中任意两条边不共享端点。相关概念:
| 概念 | 定义 |
|---|---|
| 匹配数 | |M|,即匹配中包含的边数 |
| 最大匹配 | 边数最多的匹配 |
| 完备匹配 | 覆盖某一侧全部顶点的匹配 |
| 完美匹配 | 覆盖全部顶点的匹配(要求 |X| = |Y| 且 |M| = |X|) |
| 最大权匹配 | 边带权时,权和最大的匹配(可不覆盖全部顶点) |
增广路是匹配问题中的核心结构:一条路径,起点与终点都是未匹配顶点,路径上的边交替出现"非匹配边、匹配边、…、非匹配边",长度为奇数。沿增广路把匹配边与非匹配边互换(匹配状态取反),匹配数增加 1,且匹配的合法性保持。
Berge 定理:M 是最大匹配 ⟺ M 不存在增广路。这一定理与最大流的"无增广路即为最大流"同构:两者都把最优性转化为"不存在可改进的结构",并把算法设计归结为反复寻找这种结构。
2.6.2 匈牙利算法
匈牙利算法按左侧顶点逐个尝试寻找增广路:
matchRight[] 全部置为未匹配
for u in X:
清空本次搜索的访问标记
若从 u 出发能找到一条增广路:
翻转该路径上的匹配状态,匹配数加一
返回匹配数
单次寻找用 DFS 或 BFS 实现:从一个未匹配的左顶点出发,沿非匹配边到达右顶点;若该右顶点未匹配则找到增广路,否则沿其匹配边到达左顶点并继续。为避免重复访问构成死循环,需要对访问过的顶点做标记。
复杂度 O(V·E):匹配数最多 min(|X|,|Y|),每次增广 O(E)。
2.6.3 König 定理与三个量的关系
König 定理:二分图中,最大匹配数 = 最小点覆盖数。
由此得到一组换算关系。点覆盖的补集是独立集(未覆盖任何边的顶点集合必然两两不相邻),因此:
最大独立集 = |V| − 最小点覆盖 = |V| − 最大匹配 (二分图)
最小边覆盖 = |V| − 最大匹配 (无孤立顶点)
这组关系的价值在于用一个算法回答三类问题:求最大配对、求最少选点以覆盖全部可行配对、求互不相干的顶点最大集合。在一般图上,最大匹配有多项式算法(带花树),而最小点覆盖与最大独立集是 NP-hard;二分图上三者同时可多项式求解,因此建模时应尽量把问题表达为二分图结构。
2.6.4 Hopcroft-Karp:分层与多路增广
匈牙利算法的瓶颈在于每次增广只看一条路径。Hopcroft-Karp 用与 Dinic 相同的思路批量处理:
- BFS 分层:从所有未匹配的左顶点同时出发,在交替图上按层次扩散,得到每个左顶点到最近未匹配右顶点的距离;同时判断本轮是否存在增广路。
- DFS 多路增广:只沿层次严格递增的边搜索,一轮内找出多条互不相交的最短增广路(一个极大集合)。
- 重复,直到不存在增广路。
复杂度 O(E·√V)。分析依据是两条:每轮把最短增广路长度至少增加 1,因此长度不超过 √V 的轮次最多 √V 轮;而最短增广路长度超过 √V 后,剩余的增广路条数不超过 √V(每条路径长度大于 √V 且互不相交),因此总轮数为 O(√V),每轮 O(E)。
与匈牙利算法的取舍:匈牙利算法实现更短、常数更小;Hopcroft-Karp 在稀疏大图上优势明显。
2.6.5 带权匹配与 Kuhn-Munkres
问题:边带权,求权和最大的匹配;在两侧顶点数相等且要求覆盖全部顶点时,求最大权完美匹配。
可行顶标与相等子图。为左侧每个顶点 i 赋予顶标 lx[i],右侧每个顶点 j 赋予 ly[j],若它们满足
lx[i] + ly[j] ≥ w[i][j] 对所有 (i, j) 成立
则称其为可行顶标。所有取等号的边 lx[i] + ly[j] = w[i][j] 构成的子图称为相等子图。
核心定理:若相等子图中存在完美匹配,则该匹配是最大权完美匹配。理由是任意匹配的权和不超过可行顶标之和 Σlx + Σly(每条匹配边都满足 lx[i] + ly[j] ≥ w[i][j]),而相等子图中的完美匹配恰好取到该和。
Kuhn-Munkres 算法:从一组可行顶标出发(常取 lx[i] = max_j w[i][j]、ly[j] = 0),在相等子图中用匈牙利算法找增广路;若找不到,则调整顶标使相等子图扩大,再重新搜索:
对每个左顶点 i:
在相等子图中搜索增广路
若失败:
delta = min{ lx[u] + ly[v] − w[u][v] } u 为本次搜索访问过的左点
v 为本次搜索未访问的右点
对访问过的左点执行 lx[u] -= delta
对访问过的右点执行 ly[v] += delta
重复搜索,直至找到增广路
复杂度 O(V³):每个左顶点一次增广,每次增广的顶标调整累积代价为 O(V²)。
与最小费用流的等价。把左顶点连源(容量 1、费用 0)、右顶点连汇(容量 1、费用 0)、可行配对连边(容量 1、费用为负权),求最小费用最大流即得最大权匹配。KM 是该模型在"完全二分图 + 求完美匹配"下的专用算法,常数更小;含点容量或边稀疏时费用流的建模能力更强。
2.7 建模方法
算法本身是固定的,实际困难集中在把业务约束翻译成图。以下按网络流与匹配分别给出套路。
2.7.1 网络流的常见建模套路
| 套路 | 做法 | 用途 |
|---|---|---|
| 拆点 | 把顶点 v 拆成 v_in 与 v_out,中间连一条容量为"点容量"的边 | 限制顶点被使用的次数(点容量),如顶点不相交路径、每个节点最多承担 k 个任务 |
| 超级源与超级汇 | 增设 S 连各源(容量为供给上限),各汇连 T(容量为需求上限) | 多源多汇化为单源单汇 |
| 上下界流 | 边 (u,v) 有下界 l 与上界 c;先按下界设置初始流,再对差值网络求可行流 | 表达"至少多少"的约束,如最低采购量、最少分配数 |
| 最小割转化 | 把"二选一"的划分代价写成边权,答案 = 总收益 − 最小割 | 最大权闭合子图、二值标记、项目选择 |
| 容量承载资源量 | 容量不是流量而是资源(时间、预算、带宽) | 资源分配与排程 |
| 费用承载偏好 | 用费用区分不同质量或不同成本的选择 | 最小费用分配、带偏好的匹配 |
上下界可行流的处理要点:对每条边 (u,v),设下界 l、上界 c,先令 f(u,v) = l(此时部分顶点不满足守恒),再对差值网络——边容量为 c − l——增加附加边以修复守恒:对每个顶点,按其"预流量"的净值添加与超级源或超级汇的边,最后判断超级源能否把全部预流量送出。有源汇情形还需再加一条 t → s 的无穷容量边,且"可行流"要求超级源的全部出边满载。
最大权闭合子图(最常用的最小割转化):
- 给定有向图,每个顶点有正权或负权,求权和最大的闭合子图(若选中某顶点则其后继必须全部选中)。
- 建模:源 S 连正权点,容量为该权值;负权点连汇 T,容量为该权值的绝对值;原图每条边容量为 ∞。
- 答案 = 正权总和 − 最小割。
- 含义:割断 S → 正权点表示"放弃该正权",割断负权点 → T 表示"选中该点并付出代价",容量为 ∞ 的边保证不会出现"选中前驱却放弃后继"的划分。
2.7.2 匹配问题的建图方式
| 需求 | 建图方式 | 可用的算法 |
|---|---|---|
| 每个对象最多配一次,求最多配对数 | 左连源(容量 1)、右连汇(容量 1)、可行配对连边(容量 1) | 匈牙利、Hopcroft-Karp 或最大流 |
| 考虑收益或成本,求总收益最大 | 边加权,求最大权匹配 | Kuhn-Munkres 或最小费用最大流 |
| 一个对象可接受多个配对,上限为 k | 该对象到源(或汇)的边容量设为 k | 最大流 |
| 一个任务需要多个人共同完成 | 任务的供给边容量设为人数需求 | 最大流 |
| 必须完成至少 k 个配对 | 需求下界 | 上下界流,或把对象复制为 k 个再求匹配 |
其中第一行说明匹配与流的关系:二分图最大匹配是单位容量网络最大流的特例;匈牙利算法相当于在这一特例上对 Dinic 思路的进一步特化(用 DFS 找增广路、以点为单位而非以层次为单位推进)。
2.7.3 把业务约束翻译为容量与费用的要点
- 约束的类型决定使用的元素。次数上限用容量;单位成本用费用;必须满足的下限用下界;互斥("二者只能选其一")用无穷容量边配合最小割;先后顺序用无穷容量边禁止"越过"。
- "至多"与"至少"必须区分。最大流天然表达"至多","至少"无法用最大流值直接表达,必须转为下界流,或在先扣除下界后判断可行性,或作为单独的判定条件(最小割是否小于某阈值)。
- 点在约束中的位置。约束作用在"最多通过多少"上时写在边上;作用在"该对象只能用一次"上时写在顶点上——后者需要用拆点或匹配表达,误写成边容量会得到语义错误的结果。
- 整数性前提。容量与费用取整数时,流与费用均为整数,离散分配语义成立。容量为实数时,"最多几个任务"这类语义需要自行取整;若必须表达整数决策,应使用整数容量或整数规划。
- 无解的表达方式。最大流模型总有可行解(全零流合法);若业务上存在"必须满足"的约束,应把它表达为下界并判断可行性,而不能通过比较最大流值与期望值来推断。
- 规模决定算法。顶点数与边数在 10³ 以内时 Edmonds-Karp 与匈牙利算法足够;10⁴ 以上需要 Dinic 或 Hopcroft-Karp;边数在顶点数的数十倍以内(稀疏)时邻接表的收益明显,稠密图需要评估 O(V²) 的存储与分层代价。
三、实现
3.1 强连通分量实现要点
3.1.1 Tarjan 的关键量与更新规则
四个量的职责需要分清:
- dfn[u]:首次访问的次序,从 1 递增;用 0 表示"未访问",可省去额外的 visited 数组。
- low[u]:u 及其子树能回溯到的最小 dfn,初始等于 dfn[u],在出边处理过程中更新。
- 栈:保存"已访问但所属分量尚未确定"的顶点。
- onStack[]:标记顶点是否在栈中,用于区分"回边"与"指向已完成分量的横叉边"。
三条更新规则及其易错形态:
| 边的情形 | 正确做法 | 写错的后果 |
|---|---|---|
| 树边 (u,v),v 未访问 | 递归处理 v 之后 low[u] = min(low[u], low[v]) | 忘记在子节点返回后更新,分量内顶点被拆散 |
| 回边 (u,v),v 已访问且在栈中 | low[u] = min(low[u], dfn[v]) | 用 low[v] 会把 low 拉到更早的顶点,两个分量被错误合并,分量数偏少 |
| 横叉边 (u,v),v 已访问且不在栈中 | 不更新 | 若更新则把已完成分量并入当前分量 |
其余四处易错点:
- 出栈判定的位置。必须在 u 的全部出边处理完毕之后判断 dfn[u] == low[u];放在遍历中途会提前弹栈。
- "已访问"与"在栈中"不可合并。若用
dfn[v] != 0统一处理,就会在横叉边上误更新 low。 - 弹栈循环的边界。反复弹出直到弹出 u 本身为止(含 u),不要写成"弹出到栈空"或"不含 u"。
- 迭代实现中父节点 low 的更新时机。子节点帧弹出后才更新父节点的 low,位置与递归版本一致。
3.1.2 缩点建图与入度统计
输入:原图邻接表、分量编号 comp[]、分量数 k
1. 新建 k 个顶点的邻接表 dag 与入度数组 indeg[k](初值 0)
2. 遍历原图每条边 (u, v):
若 comp[u] != comp[v]:
在 dag 中加入边 comp[u] -> comp[v]
indeg[comp[v]] += 1
否则:该边是分量内部边,忽略(自环在缩点后消失)
3. 若需要去重边(同一对分量之间存在多条边),用哈希集合记录已加入的 (cu, cv) 对
要点:
- 缩点图中的重边不影响可达性与拓扑排序,但会影响"以边为单位的计数"(路径计数、割容量计算),需要去重时用哈希集合,代价与用法见 散列表。
- 自环(u 到自身的有向边)在缩点后变成分量自身上的环,应单独统计:判定循环依赖时自环即为环,但计算入度时不应计入。
- 入度数组供拓扑排序使用(Kahn 算法:反复取出入度为 0 的顶点)。缩点图是 DAG,必然存在入度为 0 的顶点;若不存在,说明分量编号有误或把跨分量边误判为内边。
3.1.3 迭代实现以避免递归深度限制
递归实现的深度等于 DFS 树的高度,最坏为 O(V)。顶点数达到 10⁵ 以上时,Java 默认栈空间(视平台与参数而定,常见为 512 KB 至 1 MB)可能在数千到上万层调用后耗尽,表现为 StackOverflowError。两种处置方式:
- 增大线程栈:在专用线程中以指定栈大小运行,例如
new Thread(null, task, "dfs", 64L * 1024 * 1024)。改动最小,但栈上限仍是硬约束,10⁶ 量级不可靠。 - 改写为显式栈的迭代形式:把"待处理的顶点"与"当前处理到的出边下标"放进显式栈,深度只受堆内存限制,代价是常数因子上升。这一转换与 栈与队列 中"递归与调用栈的对应"一节的做法一致:递归的三个环节(进入、展开子问题、返回后处理)需要在帧中显式保存状态。
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.List;
/** Tarjan 强连通分量:迭代实现,避免深图上的递归栈溢出。 */
public class TarjanScc {
private final List<List<Integer>> graph;
private final int[] dfn; // 访问次序,0 表示未访问
private final int[] low; // 可回溯到的最小 dfn
private final int[] comp; // 分量编号,-1 表示未分配
private final int[] nextEdge; // 每个顶点当前处理到的出边下标
private final boolean[] onStack;
private final Deque<Integer> sccStack = new ArrayDeque<>();
private int timer;
private int compCount;
public TarjanScc(List<List<Integer>> graph) {
this.graph = graph;
int n = graph.size();
this.dfn = new int[n];
this.low = new int[n];
this.comp = new int[n];
this.nextEdge = new int[n];
this.onStack = new boolean[n];
Arrays.fill(comp, -1);
}
/** 返回 comp[],编号按弹栈顺序递增,即缩点图的逆拓扑序。 */
public int[] run() {
for (int v = 0; v < graph.size(); v++) {
if (dfn[v] == 0) {
dfs(v);
}
}
return comp;
}
private void dfs(int start) {
Deque<int[]> frames = new ArrayDeque<>(); // 帧:[顶点, 是否已完成首次进入]
frames.push(new int[]{start, 0});
while (!frames.isEmpty()) {
int[] frame = frames.peek();
int u = frame[0];
if (frame[1] == 0) { // 首次进入:打时间戳并入栈
dfn[u] = low[u] = ++timer;
sccStack.push(u);
onStack[u] = true;
frame[1] = 1;
}
if (nextEdge[u] < graph.get(u).size()) {
int v = graph.get(u).get(nextEdge[u]++);
if (dfn[v] == 0) {
frames.push(new int[]{v, 0}); // 树边:子节点先处理
} else if (onStack[v]) {
low[u] = Math.min(low[u], dfn[v]); // 回边:用 dfn[v]
}
} else { // 出边处理完毕
frames.pop();
if (low[u] == dfn[u]) { // 弹栈得到一个分量
int w;
do {
w = sccStack.pop();
onStack[w] = false;
comp[w] = compCount;
} while (w != u);
compCount++;
}
if (!frames.isEmpty()) { // 回到父节点,更新父节点的 low
int parent = frames.peek()[0];
low[parent] = Math.min(low[parent], low[u]);
}
}
}
}
public int componentCount() {
return compCount;
}
}
要点核对:
- 帧的第二项标记"是否已完成首次进入",避免重复打时间戳与重复入栈;
- 父节点的 low 更新发生在子节点帧弹出之后,与递归版本的位置一致;
- 栈中的顶点顺序与递归版本完全相同,因此分量编号约定也相同;
- 迭代版本的常数因子高于递归版本(每层一次数组分配),浅图或不深的正向图上递归写法更简单;两种写法的复杂度同为 O(V+E)。
3.2 最大流实现要点
3.2.1 边结构与反向边技巧
最大流实现的第一处关键设计是正向边与反向边成对存储,使两者可以通过下标异或互相定位:
/* 数组式邻接表:边成对存储,下标 i 与 i ^ 1 互为反向边。 */
#define MAXN 10005
#define MAXE 200005
int head[MAXN], nxt[2 * MAXE], to[2 * MAXE];
long long cap[2 * MAXE]; /* 残量容量:正向存容量,反向存 0 */
int edgeCount = 0;
void add_edge(int u, int v, long long c) {
to[edgeCount] = v; cap[edgeCount] = c;
nxt[edgeCount] = head[u]; head[u] = edgeCount++;
to[edgeCount] = u; cap[edgeCount] = 0; /* 反向边初始残量为 0 */
nxt[edgeCount] = head[v]; head[v] = edgeCount++;
/* 连续两次加入使正向边下标与反向边下标仅最低位不同,i ^ 1 即配对下标 */
}
void push(int i, long long d) {
cap[i] -= d;
cap[i ^ 1] += d; /* 反向边残量增加,用于撤销与改道 */
}
三个要点:
- 异或寻址的前提是成对加入。只要保证正反向边相邻加入,则
i ^ 1恒为配对下标,无需额外存储配对指针。改用对象或链表存储时需要显式保存反向边引用,这是两种实现的主要差别。 - 反向边初始残量为 0,在增广时增加。初始化时把反向边容量设为原容量是"结果偏大"的典型成因,其后果不仅是数值错误,还会使算法收敛到非法的流。
- 残量与容量共用一个数组。判断"能否走这条边"只看残量是否大于 0,不需要同时读取原容量;原容量只在建模阶段使用。
Java 中用 long[] cap 与 int[] head/next/to 平行数组的写法,在 10⁶ 条边规模下不产生对象开销;用 List<Edge> 的写法可读性更好,但每条边一个对象带来的分配与指针追逐会放大常数因子,缓存局部性的影响见 数组与链表。
3.2.2 BFS 分层与 DFS 增广
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
/** Dinic 最大流:平行数组 + 成对边 + BFS 分层 + DFS 增广 + 当前弧优化。 */
public class Dinic {
private static final long INF = Long.MAX_VALUE / 4;
private final int n;
private final int[] head;
private final int[] next;
private final int[] to;
private final long[] cap;
private final int[] level;
private final int[] iter; // 当前弧:每个顶点下一个待尝试的边下标
private int edgeCount;
public Dinic(int n, int maxEdges) {
this.n = n;
this.head = new int[n];
this.level = new int[n];
this.iter = new int[n];
int m = 2 * maxEdges;
this.next = new int[m];
this.to = new int[m];
this.cap = new long[m];
Arrays.fill(head, -1);
}
public void addEdge(int u, int v, long c) {
to[edgeCount] = v; cap[edgeCount] = c;
next[edgeCount] = head[u]; head[u] = edgeCount++;
to[edgeCount] = u; cap[edgeCount] = 0; // 反向边
next[edgeCount] = head[v]; head[v] = edgeCount++;
}
/** 在残量网络上求层次;汇点不可达时返回 false,表示已无增广路。 */
private boolean bfs(int s, int t) {
Arrays.fill(level, -1);
Deque<Integer> queue = new ArrayDeque<>();
level[s] = 0;
queue.add(s);
while (!queue.isEmpty()) {
int u = queue.poll();
for (int i = head[u]; i != -1; i = next[i]) {
if (cap[i] > 0 && level[to[i]] < 0) {
level[to[i]] = level[u] + 1;
queue.add(to[i]);
}
}
}
return level[t] >= 0;
}
/** 只沿 level[v] == level[u] + 1 的边增广,返回本次推送的流量。 */
private long dfs(int u, int t, long f) {
if (u == t) {
return f;
}
for (; iter[u] != -1; iter[u] = next[iter[u]]) {
int i = iter[u];
int v = to[i];
if (cap[i] > 0 && level[v] == level[u] + 1) {
long d = dfs(v, t, Math.min(f, cap[i]));
if (d > 0) {
cap[i] -= d;
cap[i ^ 1] += d;
return d;
}
}
}
level[u] = -1; // 本轮分层中该顶点已无法继续增广,提前剪枝
return 0;
}
public long maxFlow(int s, int t) {
long flow = 0;
while (bfs(s, t)) {
System.arraycopy(head, 0, iter, 0, n); // 每轮分层后重置当前弧
long f;
while ((f = dfs(s, t, INF)) > 0) {
flow += f;
}
}
return flow;
}
}
当前弧优化的写法。iter[u] 记录顶点 u 下一个待尝试的边下标,循环控制 for (; iter[u] != -1; iter[u] = next[iter[u]]) 使被确认为"无增广空间"的边不会被重复尝试。缺少这一步时,同一个顶点会被反复从表头扫描,单轮阻塞流的代价上升,在稠密图上表现为超时。此外,level[u] = -1 这一行把本轮已确认无法到达汇点的顶点标记出来,减少对它的再次访问,其正确性依据是:本轮中该顶点的所有出边都已尝试过,分层图未变,因此不会再出现可达汇点的边。
分层图重建。dfs 返回 0 只表示当前分层图内无增广路,必须回到 bfs 重新分层;若把"dfs 返回 0"当作算法结束,结果会偏小。反过来,若每增广一条路径就重新 BFS,虽然结果正确,但轮数大幅上升。正确的循环结构是"外层 BFS 分层、内层反复 DFS 直到返回 0",两者构成"求阻塞流"的完整过程。
3.2.3 边界与数值
- 容量上限与溢出。
INF取Long.MAX_VALUE / 4一类安全值,不要取Long.MAX_VALUE:Math.min(f, cap[i])与累加都可能溢出为负数,进而使cap[i] > 0的判断失效,增量提前停止。 - 边数组容量。数组长度按 2 × 输入边数分配;若建模时另外加入了源汇边、拆点边与上下界附加边,需把这些边一并计入。
- 递归深度。
dfs的递归深度不超过层次数(≤ V)。V 为数万时递归可能触发栈溢出,深图应改为迭代增广或改用其他算法。 - 顶点编号。源、汇与业务顶点共用一个编号空间;把源汇固定为 0 与 n−1 时要注意数组按最大编号 + 1 分配,避免源汇编号与业务顶点冲突。
- 重边与自环。重边允许(等价于容量相加,逐条加入即可);自环对最大流无贡献,应跳过,以免污染分层。
3.3 费用流实现要点
3.3.1 费用边的存储与增广
在容量的基础上增加费用字段,反向边费用取负:
from collections import deque
class MinCostFlow:
"""最小费用最大流:SPFA 求最短路,逐次沿最短增广路推流。"""
def __init__(self, n):
self.n = n
self.head = [-1] * n
self.to = []
self.nxt = []
self.cap = []
self.cost = []
self.edge_count = 0
def add_edge(self, u, v, cap, cost):
self.to.append(v); self.cap.append(cap); self.cost.append(cost)
self.nxt.append(self.head[u]); self.head[u] = self.edge_count
self.edge_count += 1
self.to.append(u); self.cap.append(0); self.cost.append(-cost) # 反向边费用取负
self.nxt.append(self.head[v]); self.head[v] = self.edge_count
self.edge_count += 1
def solve(self, s, t):
"""返回 (最大流, 最小费用)。"""
INF = float('inf')
total_flow = 0
total_cost = 0
while True:
dist = [INF] * self.n
in_queue = [False] * self.n
pre_edge = [-1] * self.n
dist[s] = 0
queue = deque([s])
in_queue[s] = True
while queue: # SPFA 处理负权
u = queue.popleft()
in_queue[u] = False
e = self.head[u]
while e != -1:
v = self.to[e]
if self.cap[e] > 0 and dist[u] + self.cost[e] < dist[v]:
dist[v] = dist[u] + self.cost[e]
pre_edge[v] = e
if not in_queue[v]:
queue.append(v)
in_queue[v] = True
e = self.nxt[e]
if dist[t] == INF:
break # 不存在增广路
bottleneck = INF # 回溯路径求瓶颈
v = t
while v != s:
e = pre_edge[v]
bottleneck = min(bottleneck, self.cap[e])
v = self.to[e ^ 1]
v = t
while v != s: # 更新残量
e = pre_edge[v]
self.cap[e] -= bottleneck
self.cap[e ^ 1] += bottleneck
v = self.to[e ^ 1]
total_flow += bottleneck
total_cost += dist[t] * bottleneck
return total_flow, total_cost
要点:
pre_edge[v]记录到达 v 的入边下标,回溯时用to[e ^ 1]取该边的起点;把pre_edge存成"顶点对"或"前驱顶点"会使反向边的定位变得含混,容易在多条重边时取错边。- 反向边费用为
-cost,这是"撤销流量并退回费用"的机制。把反向边费用写成 0 会使费用结果偏大,路径选择也会偏离最优。 - 累加费用使用当前轮的真实最短路费用(
dist[t])乘瓶颈流量,不要混入势函数中间量。 - SPFA 的耗时特征:入队次数与图的费用分布强相关,最坏情况下退化明显。规模较大或费用分布不易收敛时,改用势函数加 Dijkstra。Dijkstra 的实现与优先队列的用法见 堆与优先队列。
3.3.2 势函数初始化与更新
初始:用 SPFA 求一次 s 到各点的最短距离作为势 h[]
(若所有边费用非负,取 h[] ≡ 0 即可)
每轮:
1. 以 w'(u, v) = w(u, v) + h[u] - h[v] 为权,用 Dijkstra 求 dist[]
2. 若 t 不可达,算法结束
3. 本轮真实最短路费用 = dist[t] + h[t] - h[s](用更新前的 h)
4. 沿 pre_edge 回溯,增广瓶颈流量,累加 真实费用 × 瓶颈
5. 对 dist[v] 有限的顶点执行 h[v] += dist[v]
四处细节:
- 初始势必须由 SPFA/Bellman-Ford 给出(存在负费用边时)。若存在负费用边却取 h ≡ 0,reduced cost 可能为负,Dijkstra 给出的"最短路"不正确,表现为费用结果偏大或路径选择异常。
- 只更新可达点的势。
dist[v]为无穷的顶点保持原势;若把不可达点的 dist 当作 0 更新,会破坏后续轮次 reduced cost 的非负性。由于 t 不可达时算法已结束,实际需要更新的恰是本轮可达的全部顶点。 - 增广后新增的残量边满足非负性。增广路径上的边在更新后的势下 reduced cost 为 0,其反向边因此也为 0,不会引入负权。这是 Johnson 技巧在费用流中的核心不变式,也是"初始无负环"这一前提必须成立的原因。
- 浮点费用。费用为浮点数时,势的非负性只在小误差范围内成立,Dijkstra 的严格正确性下降;整数费用是更稳妥的选择,需要按比例缩放时把费用整体放大为整数。
3.3.3 负费用边与负环的处理
- 负费用边的存在不等于无解。只要残量网络中没有可达的负环,最小费用最大流仍有有限最优解;负费用边只是要求初始势由 SPFA 给出。
- 可达负环导致费用无下界。此时无论流量如何,都可以沿环反复循环推送使费用不断下降,问题没有有限解。处置方式是在建模阶段消除:给环上至少一条边的费用加上正的下界并相应调整其他费用,或把"必须沿环循环"的业务语义改为显式约束(例如加入流量需求,使环上的推送不再"免费")。
- SPFA 需要终止条件。缺少"每个顶点入队次数上限"判断的实现,遇到可达负环时队列永不为空,表现为程序不返回。至少应加入队计数并在超过 V 次时中止并报错,而不是继续循环。
- 负环检测的成本。若在每轮增广前做一次负环检测,代价为 O(V·E),会显著放大总耗时。更常见的做法是在建模与测试阶段用小规模实例验证无负环,线上运行只保留终止条件作为兜底。
3.4 二分图匹配实现要点
3.4.1 匈牙利算法的递归实现与访问标记重置
import java.util.Arrays;
import java.util.List;
/** 二分图最大匹配:匈牙利算法(对每个左侧顶点求一条增广路)。 */
public class Hungarian {
private final List<List<Integer>> adj; // 左侧顶点 -> 相邻的右侧顶点
private final int[] matchRight; // 右侧顶点 -> 匹配的左侧顶点,-1 表示未匹配
private final int[] visitedAt; // 右侧顶点的访问时间戳
private int stamp; // 当前轮的标记值,代替逐轮清空数组
public Hungarian(List<List<Integer>> adj, int rightCount) {
this.adj = adj;
this.matchRight = new int[rightCount];
this.visitedAt = new int[rightCount];
Arrays.fill(matchRight, -1);
}
public int maxMatching() {
int matched = 0;
for (int u = 0; u < adj.size(); u++) {
stamp++; // 每个左侧顶点开始一次新的搜索
if (augment(u)) {
matched++;
}
}
return matched;
}
/** 从左侧顶点 u 出发寻找一条增广路。 */
private boolean augment(int u) {
for (int v : adj.get(u)) {
if (visitedAt[v] == stamp) { // 本轮已访问,跳过以免重复与死循环
continue;
}
visitedAt[v] = stamp;
if (matchRight[v] == -1 || augment(matchRight[v])) {
matchRight[v] = u; // 找到增广路:翻转匹配
return true;
}
}
return false;
}
}
要点与易错形态:
- 访问标记必须只对当前这次搜索有效。用时间戳(
stamp每轮加一)代替每次Arrays.fill,把清空代价从 O(V) 降为 O(1)。若标记全局保留且不清空,后续搜索会被上一轮的访问痕迹阻塞,结果偏小;若每轮清空但用布尔数组,正确但常数较大。 - 标记对象是右侧顶点,不是左侧顶点。左侧顶点的重复访问由匹配关系控制(递归沿
matchRight[v]回溯),标记右侧顶点即可保证每个右侧点在同一轮搜索中只被展开一次;对左侧顶点也做标记会切断沿匹配边回溯的路径。 - 递归深度不超过左侧顶点数。一般规模无需迭代化;左侧顶点达到 10⁵ 时递归深度可能触发栈溢出,应改用 Hopcroft-Karp 或增大专用线程栈。
- 要求最大权匹配时不能用匈牙利算法,需要 Kuhn-Munkres 或转为最小费用最大流(3.4.3)。
- 前置条件是输入为二分图。若输入含奇环,匈牙利算法的结果既不是最大匹配也不是任何有定义的量。二分图判定用染色法(DFS 交替染色,遇到同色相邻即存在奇环),代价 O(V+E),应在入口处校验。
3.4.2 Hopcroft-Karp 的分层与多路增广
from collections import deque
def hopcroft_karp(adj, n_left, n_right):
"""adj:左侧顶点 -> 相邻右侧顶点列表;返回最大匹配数。"""
INF = float('inf')
match_left = [-1] * n_left
match_right = [-1] * n_right
dist = [0] * n_left
def bfs():
"""从所有未匹配左点出发分层,返回本轮是否存在增广路。"""
queue = deque()
for u in range(n_left):
if match_left[u] == -1:
dist[u] = 0
queue.append(u)
else:
dist[u] = INF
found = False
while queue:
u = queue.popleft()
for v in adj[u]:
w = match_right[v]
if w == -1:
found = True # 到达未匹配右点,本轮存在增广路
elif dist[w] == INF:
dist[w] = dist[u] + 1
queue.append(w)
return found
def dfs(u):
"""沿层次递增的边寻找增广路,成功则翻转匹配。"""
for v in adj[u]:
w = match_right[v]
if w == -1 or (dist[w] == dist[u] + 1 and dfs(w)):
match_left[u] = v
match_right[v] = u
return True
dist[u] = INF # 本轮该点无法再增广,后续不再访问
return False
matching = 0
while bfs():
for u in range(n_left):
if match_left[u] == -1 and dfs(u):
matching += 1
return matching
要点:
- 分层只负责给出"最短增广路的长度"。
dist记录左侧顶点在交替图中的层次;BFS 遇到未匹配右点时记录"存在增广路"但不继续向其扩展,以保证本轮处理的都是长度相同的增广路。 - 一轮 DFS 找多条不相交增广路。路径长度相同且顶点互不相交,因此可以共用一次分层的结果,这是相对匈牙利算法的主要收益。
dist[u] = INF的剪枝不可省略。否则同一顶点会在同一轮被反复搜索,最坏退化为匈牙利算法的复杂度。- 轮数上界为 O(√V):每轮最短增广路长度至少增加 1;长度超过 √V 后剩余增广路不超过 √V 条。总复杂度 O(E·√V)。
3.4.3 带权匹配的实现难点
带权二分图最大权匹配的两条实现路径:
| 路径 | 做法 | 复杂度 | 适用 |
|---|---|---|---|
| Kuhn-Munkres | 顶标 + 相等子图 + 增广;调整顶标扩大相等子图 | O(V³) | 完全二分图、求最大权完美匹配,常数小 |
| 最小费用最大流 | 左连源、右连汇、配对边费用取负权 | O(F·E·log V) | 边稀疏、含点容量或其他流约束 |
Kuhn-Munkres 的四处实现难点:
- 增广路搜索需要两套访问标记(左顶点与右顶点各一套),且同样要按轮重置。只标记右顶点会把已经尝试失败的左顶点重复展开,复杂度退化。
- delta 必须与 slack 数组同步更新。常见写法是为每个右顶点维护
slack[v] = min(lx[u] + ly[v] − w[u][v])(u 取本次搜索访问过的左点),调整顶标时对访问过的左点lx[u] -= delta、对访问过的右点ly[v] += delta,并同步更新未访问右顶点的 slack;漏掉 slack 的更新,下一轮的 delta 判断就会错误。 - 图不是完全二分图时需要补边。KM 通常要求两侧顶点数相同且任意两点之间有边;缺失的边补 0 权(求最大权完美匹配时等价于允许该位置不产生收益),或补一个绝对值有限的大负数(要求必须匹配全部顶点时)。补 −∞ 时需防止溢出。
- 求最小权匹配时不能简单取负后沿用初始化。取负后存在负权边,初始顶标
lx[i] = max_j w[i][j]可能为负,应严格按可行顶标的定义重算(也可以改用最小费用流,省去顶标细节)。
3.5 复杂度与实测
3.5.1 各算法复杂度与适用规模
| 问题 | 算法 | 复杂度 | 适用规模与前提 |
|---|---|---|---|
| 强连通分量 | Kosaraju | O(V+E) | 需反向图,空间约两倍边数 |
| 强连通分量 | Tarjan | O(V+E) | 一次 DFS,需栈与 low 数组;递归深度 O(V) |
| 2-SAT | 蕴涵图 + 强连通分量 | O(n+m) | 变量数 10⁶ 量级可行,前提是字句长度不超过 2 |
| 最大流 | Ford-Fulkerson(DFS 选路) | O(E·|f|) | 仅理论参照,容量为大整数时不可用 |
| 最大流 | Edmonds-Karp | O(V·E²) | V 在数百以内,实现最短 |
| 最大流 | Dinic | O(V²E) | V 在 10³ 至 10⁴,通用首选 |
| 最大流 | Dinic(单位容量) | O(E·min(V^{2/3}, √E)) | 每条边容量为 1 |
| 最大流 | Dinic(二分图匹配) | O(E·√V) | 源汇边容量为 1 |
| 最小费用最大流 | SSP + SPFA | O(F·V·E) | 流量值 F 不大 |
| 最小费用最大流 | SSP + Dijkstra + 势函数 | O(F·E·log V) | 同上;含负权边时须先求初始势 |
| 二分图最大匹配 | 匈牙利 | O(V·E) | V 在数千以内,实现最短 |
| 二分图最大匹配 | Hopcroft-Karp | O(E·√V) | 稀疏大图,10⁵ 量级可行 |
| 带权二分图匹配 | Kuhn-Munkres | O(V³) | 两侧顶点数相等,数千以内 |
| 带权二分图匹配 | 最小费用最大流 | O(F·E·log V) | 稀疏图,需同时表达容量约束 |
三点判读:
- F 的口径。SSP 的复杂度以增广次数 F 计数。容量为整数时每次增广至少推送 1 个单位,故 F 不超过最大流值;容量大而流量值小、或容量为 1 的匹配类问题,F 都较小。若容量与流量值都很大,SSP 的耗时可能远超 Dinic。引用该结论时必须说明 F 的定义。
- 复杂度界与实测的差距。O(V²E) 是最坏情况的上界,随机图与常见建模图远达不到;反之,分层结构退化的构造图可以达到该上界。规模评估应以目标数据形态的实测为准。
- 实数运算与整数运算。费用流中的势函数在浮点费用下只近似满足非负性,实际耗时与结果精度都可能偏离分析结论;复杂度表不含浮点误差带来的额外分支与舍入处理。
3.5.2 实测方法
最大流与匹配的实测有两处特殊:输入是图结构而非数组,且耗时对图的形态高度敏感。
- 图的生成方式必须与目标一致。随机均匀图与建模图(网格、二分图、分层图、链状图)上的耗时差异可达数量级。基准应使用从真实业务抽取或用同一规则合成的图,并在结论中说明图的类型、顶点数、边数与容量分布。
- 规模参数化。按顶点数(10³、10⁴、10⁵)与平均度数(稀疏、稠密)两个维度展开,观察耗时随规模的变化趋势。JMH 的
@Param可以直接声明这两类维度并按组合展开,写法与判读方式见 JMH 微基准测试。 - 容量分布作为对照维度。全部容量为 1(单位容量)、容量为小整数、容量为大整数三类输入下,Dinic 与 SSP 的相对表现不同;容量为大整数时,Ford-Fulkerson 的"每次推送 1 个单位"行为会直接暴露。
- 记录与语言无关的计数。增广次数、分层轮数、DFS 调用次数这三个计数在算法之间可比,且不受 JIT 与缓存状态影响,是区分"常数差异"与"量级差异"的关键证据。总耗时受即时编译层级与缓存状态影响,单点数值不足以定位问题,相关的测量陷阱见 复杂度与算法分析 中理论与实测的差异一节。
- 递归与迭代的对照。改写为迭代后常数因子的上升幅度需要实测确认;同时用深链图输入验证递归版本不栈溢出,栈溢出的证据读取与诊断手段见 应用诊断与调优。
- 内存口径。邻接表按 2 × 边数存储正反向边,费用流再多一个费用数组;平行数组实现的常驻内存约与边数成正比,对象实现的额外开销来自每条边一个对象及其引用。服务级容量与延迟结论需在压测环境中给出,方法见 linux: 压测与性能基线。
3.6 应用案例
3.6.1 依赖环检测与模块分层
模块、包、类之间的依赖构成有向图,构建系统与静态分析工具需要回答两类问题。
环检测。对依赖图求强连通分量,存在大小大于 1 的分量或存在自环即存在循环依赖。相比"DFS 找环",强连通分量的优势是给出同一环上的全部成员:修复循环依赖需要完整成员集合(谁依赖谁、从哪一处断开),而 DFS 通常只报出找到的第一个环。因此缩点后的分量大小是更合适的判定依据。规模达到数十万类时,O(V+E) 的 Tarjan 是唯一能在编译期完成的选择。
分层。对缩点图做拓扑排序(用缩点建图时统计的入度数组驱动 Kahn 算法),得到的层序即合法的构建顺序与允许的依赖方向。同一分量内的成员无法排出先后,必须整体处理,常见处置是合并模块、提取公共接口、或引入回调反转依赖方向。
架构约束的代码化方式(分层与依赖方向、包边界、循环依赖禁止、公共模块依赖限制)与违规形态的对照见 Java 代码质量与静态分析 中架构约束的代码化一节;把约束写成可执行规则还是可读性更好的断言代码,该节给出取舍依据。需要注意该节指出的一点:循环依赖在编译期不报错,只在归档与部署阶段表现为模块无法独立构建,因此需要专门的检测规则,而强连通分量检测正是这类规则的核心实现。
3.6.2 任务分配与调度
任务与执行者(人员、机器、线程、服务实例)之间的可行分配构成二分图,边表示"该执行者可以承担该任务"。
| 需求 | 模型 | 算法 |
|---|---|---|
| 尽可能多地分配,每个执行者最多一个任务 | 二分图最大匹配 | 匈牙利或 Hopcroft-Karp |
| 考虑收益或成本,求总收益最大 | 带权匹配或最小费用最大流 | Kuhn-Munkres 或费用流 |
| 一个执行者可承担多个任务,不超过其能力上限 | 右顶点到汇的边容量设为上限 | 最大流 |
| 任务需要至少 k 个执行者 | 需求下界 | 上下界流,或把任务复制成 k 个再求匹配 |
| 任务之间存在先后依赖 | 依赖转为偏序约束,配合拓扑序 | 缩点 + 拓扑排序后再按序分配 |
| 任务之间存在互斥(不能同时在同一资源上) | 互斥转为无穷容量边配合最小割 | 最大流 / 最小割 |
要点:
- "每个执行者最多一个任务"是顶点上的约束,用匹配表达比用边的容量表达更直接;执行者容量大于 1 时匹配不再适用,应转为最大流,并在右顶点到汇的边上写容量。
- 成本最小与收益最大是同一问题的两种表述,取负即可互换;但负权会带来额外处理:费用流需先求初始势,KM 需按可行顶标的定义重算初始顶标。
- 图规模常由任务数决定,而执行者数可能很大。把能力集相同的执行者合并为一个带容量的节点,可以在不改变最优值的前提下压缩图规模。
- 线程池与并发调度的运行期语义(容量、拒绝策略、公平性、队列积压)见 Java 并发编程;本文处理的是静态分配问题的求解,不涉及运行期调度实现。
3.6.3 资源分配与容量规划
供给与需求之间的可输送关系构成流网络:源侧节点代表供应上限,汇侧节点代表需求上限,中间节点代表中转能力,边的容量代表通道容量。
- 最大可满足的需求量。把全部需求连到汇,求最大流即为当前容量下最多能满足的需求。未满足的部分由最小割指出瓶颈:割集中的边就是扩容收益最大的那批通道。
- 扩容决策的定量判据。最小割给出一个边集合,其容量之和恰等于当前最大流。只有在瓶颈集合整体扩容时最大输送量才会提升;在非瓶颈通道上扩容不产生收益。这把"该给哪条链路加带宽"从经验判断变为可计算的结论。
- 节点自身容量。中转节点的处理能力用拆点表达(v_in → v_out 的边容量等于节点处理上限),避免"通道足够但节点过载"的建模错误。
- 资源不可分割时的口径。容量与费用取整数时流为整数,可直接对应"多少个单位"的资源;资源可分割时容量可以是实数,但结论只对可分的语义成立。
3.6.4 推荐与配对
推荐与配对类业务的常见形态是两类实体之间的可行配对及偏好权重。
- 双向选择的配对(求职者与岗位、供需双方):无权重时用最大匹配求最大配对数量;有权重(匹配度、预计收益)时用带权匹配最小化总成本或最大化总收益。
- 与稳定匹配的区别。稳定匹配(Gale-Shapley)要求不存在互相偏好更甚的"私奔对",其目标是稳定性而非配对数最大;最大权匹配允许牺牲个别对象的偏好以换取整体收益最优。两者目标不同,不能互相替代,选用依据是业务能否接受"整体最优但个体不满意",以及偏好是否必须被尊重。
- 配对数受可行性图结构限制。可行边稀疏(每个对象只有少数可配对象)时,最大匹配通常远小于 min(|X|, |Y|);此时提升配对数需要放宽可行性条件(扩大可配范围),而不是改进匹配算法。
- 阈值与候选集。把"匹配度低于阈值不可配"作为建图条件时,阈值的选择直接决定了可行边的规模,也决定了匹配算法的规模前提;阈值过高会使图变得稀疏,可能连最大匹配都无法覆盖需求。
3.6.5 数据分片与副本放置的建模思路
分片与副本的放置可以表达为带容量与费用的流模型,用于评估放置方案的可行性与代价。
- 副本数要求。每个分片必须放置 k 个副本,表达为分片节点的供给量为 k(或把分片复制为 k 个需求节点)。
- 节点容量。每个存储节点能承载的分片数有上限,表达为节点到汇的边容量;容量规划的口径(单分片目标容量、写入吞吐、增长系数、预分片与映射解耦)见 分库分表与全局唯一 ID 中容量与扩容一节。
- 放置代价。跨机架、跨机房的流量代价表达为边的费用,用最小费用流求总代价最低的放置方案。
- 迁移与重平衡。已放置的副本表达为下界(必须保留),或在费用上给予优待(倾向保留);迁移代价表达为改动的费用。用费用流求解,可在满足副本数与容量约束的前提下最小化搬迁量,与扩容搬迁的两种形态(调整映射、增加分片数)对应。
- 可行性判定。当节点容量与副本数约束互斥(总容量不足,或某分片的所有候选节点已满)时,流模型无解,这正是容量规划阶段需要提前发现的情况。
这类模型的规模通常是"分片数 × 候选节点数"条边:分片数在 10³ 至 10⁴、候选节点在 10² 至 10³ 量级时,Dinic 或费用流的单次求解可以放在规划任务中离线执行,不必进入在线路径。
3.7 常见问题与排查
| 现象 | 可能原因 | 验证与处置 |
|---|---|---|
| 最大流结果明显偏小,且与容量分布相关 | 反向边未加入;反向边初始残量被设成原容量;增广时只更新正向边 | 检查加边函数是否成对加入;检查增广处是否同时执行 cap[i] -= d 与 cap[i ^ 1] += d;用含"绕行改道"的用例(两层菱形结构)验证反向边生效 |
| 最大流结果偏大或超过所有割的容量 | 反向边初始容量不为 0;割容量计算把 T→S 的边也计入 | 打印全部正向边容量之和作为上界对比;确认割容量只累加 S→T 方向 |
| Dinic 在未达到最大流时提前结束 | DFS 返回 0 被当作算法结束,未回到 BFS 重新分层;或分层条件写成 level[v] <= level[u] | 检查外层循环为 while (bfs(s, t))、内层为 while ((f = dfs(...)) > 0);分层判定必须严格等于 level[u] + 1 |
| Dinic 在稠密图上耗时异常 | 缺少当前弧优化,单轮内反复从表头扫描;或每增广一条路径就重新 BFS | 加入 iter[] 并在每轮分层后重置;用分层轮数计数器确认轮数是否异常偏多 |
深图上抛 StackOverflowError | SCC、费用流回溯或 Dinic 的 DFS 使用递归,深度达到 O(V) | 查看异常栈顶是否落在 DFS 方法;改为显式栈的迭代实现(3.1.3)或增大专用线程栈;线程栈与转储的读取方式见 应用诊断与调优 |
| 费用流不返回或耗时爆炸 | 残量网络中存在可达负环;或 SPFA 缺少入队次数上限 | 检查反向边费用是否为 −cost、是否存在总费用为负的环;给 SPFA 加入队计数,超过 V 次时中止并报错 |
| 费用流结果比预期大 | 势函数未用 SPFA 初始化(存在负权边却取 h ≡ 0);累加费用时误用 reduced cost 而未还原为真实费用 | 确认累加的是"真实最短路费用 = dist[t] + h[t] − h[s]";确认初始势由 SPFA 给出 |
| 每轮增广量恒为 1,耗时远高于预期 | 建模时把边容量写成 1;或瓶颈计算取自反向边(pre_edge 与反向边下标混淆) | 打印每轮的瓶颈值;检查瓶颈回溯使用的是 cap[pre_edge[v]] 而非 cap[pre_edge[v] ^ 1] |
| 二分图匹配结果偏小 | 访问标记未按每个左侧顶点重置;标记对象错为左侧顶点;输入不是二分图(存在奇环) | 用"标记计数器每轮递增"的方式实现;用染色法校验输入;构造一侧点数多于另一侧的用例,确认上限为 min(|X|, |Y|) |
| 带权匹配结果与最小费用流结果不一致 | KM 中 delta 与 slack 未同步更新;非完全二分图时补边策略不统一 | 用同一输入分别跑 KM 与费用流,比较权和;补边统一为 0 权或有限大负数,不混用 |
| 2-SAT 判定可满足但构造的赋值不满足约束 | 取值规则与分量编号约定不匹配(Tarjan 编号是逆拓扑序,Kosaraju 是拓扑序) | 固定一种编号约定并写单测:随机小规模实例用穷举赋值与算法结果对照;或在缩点图上显式拓扑排序后按逆序赋值 |
| 强连通分量数量偏少 | 回边更新 low 时用了 low[v] 而非 dfn[v];或在横叉边(已访问且不在栈中)上错误更新 low | 用"两个互不可达但共享后继"的图验证分量数;核对三条更新规则的适用条件 |
| 缩点后拓扑排序无法开始(不存在入度为 0 的顶点) | 分量编号错误导致把跨分量边误判为分量内边;或自环被计入入度 | 打印缩点图的顶点数与边数并与预期对照;自环单独统计,不参与入度 |
| 结果数值正确但语义不可用 | 遗漏容量约束(某资源被重复使用);遗漏"至少"下界;点容量未拆点 | 用极端输入做语义校验:小规模最优解逐项对照业务约束,检查是否出现同一对象被重复分配、下限未被满足;确认所有"至少"约束都已转为下界或可行性判定 |
| 大容量下出现负流量或提前终止 | INF 取值过大导致 Math.min 与累加溢出;容量数组用 int 而容量之和超出范围 | 全程使用 long;INF 取类型上限的四分之一以内;给流值加上"不超过源点出边容量之和"的断言 |
排查这类问题的通用手段是把不变式打印出来,而不是继续按代码阅读推测:
- 残量守恒。对每条原始边,正向残量与反向残量之和应等于原始容量;对每个中间顶点,净流出应为 0(用流量而非残量计算)。
- 流的可行性。任何时刻的流值不超过任意割的容量;最大流时用 BFS 从 s 出发的可达集构造割,验证割容量等于流值。
- 分量划分。随机选取同一分量内的两点验证双向可达,选取不同分量的两点验证至少一个方向不可达。
- 匹配的有效性。验证每条匹配边的两个端点都未被其他匹配边使用;结果不超过 min(|X|, |Y|);与暴力枚举对照。
- 增广计数。记录增广次数、分层轮数、每轮推送量,与复杂度结论对照;异常大或异常小的计数通常指向建模或更新错误,而不是性能问题。
小规模随机对照是最有效的一步:在顶点数不超过 10 的随机图上,用暴力枚举(子集枚举求最小割、全排列求最大匹配、穷举赋值求 2-SAT)验证算法结果,能在实现阶段把上述大部分问题暴露出来,代价极低。
3.8 检查清单
3.8.1 算法选型对照表
| 问题类型 | 是否需要费用或权重 | 规模 | 推荐算法 |
|---|---|---|---|
| 有向图结构划分、环检测、依赖分层 | 否 | 任意 | Tarjan 或 Kosaraju(O(V+E)) |
| 二字句布尔约束求解 | 否 | 变量数 10⁶ 以内 | 蕴涵图 + Tarjan |
| 最大输送量、可行性、最小割 | 否 | V 在数百以内 | Edmonds-Karp(实现最短) |
| 最大输送量、可行性、最小割 | 否 | V 在 10³ 至 10⁴ | Dinic(加当前弧优化) |
| 最大输送量、单位容量网络 | 否 | 每条边容量为 1 | Dinic(O(E·min(V^{2/3}, √E))) |
| 固定流量下的最小代价 | 是 | 流量值与边数不大 | SSP + Dijkstra + 势函数 |
| 固定流量下的最小代价 | 是 | 含负权边且规模小 | SSP + SPFA |
| 二分图最大配对 | 否 | V 在数千以内 | 匈牙利(实现最短) |
| 二分图最大配对 | 否 | 稀疏大图 | Hopcroft-Karp |
| 二分图带权配对(完全图) | 是 | 两侧点数相等、数千以内 | Kuhn-Munkres |
| 二分图带权配对(稀疏,含点容量) | 是 | 边稀疏 | 最小费用最大流 |
| 一般图最大匹配 | 否 | 任意 | 带花树(Blossom),不得用匈牙利算法代替 |
3.8.2 实现自检项
强连通分量
- 回边更新使用 dfn[v] 而非 low[v];已访问但不在栈中的顶点不做更新。
- 出栈判定位于全部出边处理完毕之后;弹栈范围包含 u 本身。
- 缩点建图时过滤分量内边;自环的处理方式明确(单独统计,不计入入度)。
- 深图场景评估过递归深度;提供了迭代实现或增大了专用线程栈。
最大流
- 正向边与反向边成对加入;反向边初始残量为 0;增广时两侧同时更新。
- 分层条件为
level[v] == level[u] + 1;汇点不可达时结束外层循环。 - 当前弧数组在每轮分层后重置;DFS 返回 0 时回到 BFS 而不是结束算法。
- 容量类型与 INF 取值不存在溢出;边数组按 2 × 边数(含建模附加边)分配。
- 用"源点出边容量之和"与"任一割的容量"对最大流值做过断言。
费用流
- 反向边费用为 −cost;累加费用使用真实最短路费用乘瓶颈。
- 存在负权边时初始势由 SPFA/Bellman-Ford 给出;势只对可达点更新。
- SPFA 或负环检测存在终止条件;可达负环在建模阶段被排除。
- 每轮瓶颈由 pre_edge 正确回溯,未与反向边混淆。
二分图匹配
- 访问标记按每个左侧顶点重置(时间戳写法);标记对象为右侧顶点。
- 输入被校验为二分图;结果不超过 min(|X|, |Y|)。
- 带权匹配的顶标与 slack 同步更新;非完全图的补边策略统一。
- 递归深度在可接受范围内;大图改用 Hopcroft-Karp。
建模
- 每条业务约束都能指出对应的容量、费用或下界。
- "至少"类约束已转为下界或可行性判定,未通过比较最大流值推断。
- 点上的次数限制用拆点表达,未误写成边容量。
- 容量与费用为整数,因而流值为整数,离散分配语义成立。
- 用小规模暴力对照验证过建模与实现的一致性。
结论与文档
- 复杂度结论标注了 F 或轮数的口径与前提(单位容量、完全二分图等)。
- 实测结论带有图类型、顶点数、边数与容量分布等条件。
- 使用"更快"或"更优"的表述时,给出了比较对象与成立的规模区间。
四、总结
三类问题的统一视角。 强连通分量处理"可达关系不对称时的分组",网络流处理"容量约束下的整体输送",二分图匹配处理"顶点唯一性约束下的配对"。三者共用同一套方法论:先用定理刻画最优解的判别条件(缩点无环、残量网络无增广路、匹配无增广路),再把算法设计为反复消除违反条件的最小结构(弹出分量、增广路径、翻转匹配、调整顶标),最后由对偶关系(最大流等于最小割)或组合恒等式(最大匹配等于最小点覆盖)把不同问题联系起来。
强连通分量。 强连通是等价关系,因此给出有向图唯一的划分;Kosaraju 用两次 DFS 与完成序实现,Tarjan 用一次 DFS 与时间戳、栈、low 值实现,两者复杂度同为 O(V+E),差异在常数、实现难度与分量编号顺序。缩点图一定是 DAG,这使强连通分量成为依赖分析与环检测的标准工具,其相对 DFS 找环的优势是给出完整的环成员集合。
2-SAT。 把每个字句展开为两个蕴涵得到 2n 个顶点的蕴涵图;可满足性等价于"变量与其否定不在同一强连通分量";取值由缩点后的拓扑序决定。字句长度从 2 增加到 3 使问题从 P 跳到 NP-complete,这是问题结构决定可解性的直接例子,也说明建模时把约束控制在两个文字以内具有实际价值。
最大流与最小割。 残量网络与增广路给出算法框架,割给出流值的上界,"最大流等于最小割"把优化问题与划分问题等价起来。Ford-Fulkerson 只确定框架,其复杂度依赖容量值;Edmonds-Karp 用 BFS 固定选路使复杂度与容量值脱钩;Dinic 用分层图与阻塞流把轮数降到 O(V),用当前弧把单轮代价降到 O(V·E)。单位容量网络上的 O(E·min(V^{2/3}, √E)) 与二分图匹配上的 O(E·√V) 说明问题结构可以直接改善界的量级,也说明函数签名相同的算法在不同输入类上不是同一个复杂度结论。
费用流。 在容量之外引入单位费用后,目标变为"最大之中最省"。连续最短路增广是基本方法,其正确性前提是残量网络无负环;难点在于反向边带来负权,SPFA 直接处理负权但常数与最坏情况较差,势函数用一次初始最短路把负权转换为非负权以便使用 Dijkstra。可达负环使问题无下界,这类结构必须在建模阶段消除,而不是在算法中兜底。
二分图匹配。 Berge 定理给出算法骨架,匈牙利算法按左侧逐点求增广路,Hopcroft-Karp 按轮批量求最短增广路。König 定理把最大匹配、最小点覆盖、最大独立集联系起来,使一个算法可以回答三类问题。带权匹配由 Kuhn-Munkres 用顶标与相等子图在 O(V³) 内解决,其建模等价物是最小费用最大流;两者的选择依据是图是否完全、是否还有容量类约束。
建模的分量高于算法。 上述算法的实现形态相对固定,实际困难集中在把业务约束翻译成容量、费用与下界:次数上限用容量,单位成本用费用,顶点唯一性与点次数用拆点或匹配,互斥与二选一用无穷容量边配合最小割,"至少"用下界或可行性判定,多源多汇用超级源汇。翻译错误不会引起程序报错,只会给出语义上不可用的结果,因此小规模暴力对照是必要的验证步骤。
实现的三处共性陷阱。 反向边(成对存储、初始残量为 0、两侧同时更新)是流类算法的正确性核心;递归深度(SCC、Dinic 的 DFS、费用流回溯、匈牙利算法)在深图或大图上以栈溢出的形式暴露,需要迭代实现或增大栈空间;负权与负环只出现在费用流中,其处置落在建模阶段与势函数初始化两处。三者的共同特征是"错误不表现为崩溃而表现为结果偏差",因此不变式自检与小规模对照比阅读代码更有效。
复杂度与实测。 复杂度表给出界的量级与前提(容量是否为 1、图是否为完全二分图、F 的口径、是否含浮点费用),实测给出特定图形态下的数值。图算法的耗时对图的形态高度敏感,随机图与业务图的结论不可互换;增广次数与分层轮数这类与语言无关的计数,比总耗时更能揭示量级差异的来源。二者的分工与 复杂度与算法分析 中给出的口径一致:量级不同且规模足够大时依分析决策,量级相同或落在交叉点附近时必须实测。
一条延伸的线索。 图算法至此形成脉络:遍历回答"能否到达",最短路回答"以何代价到达",最小生成树回答"以最小总代价连通",强连通分量回答"哪些顶点构成不可分割的整体",网络流与匹配回答"在容量与唯一性约束下最多能做到多少、以何代价"。它们共同的技术基础是把组合结构转化为可增量改进的对象(路径、增广路、割、匹配),并证明不存在进一步改进的可能——这正是从可行解走向最优解的通用路径。