← 线性规划网络流 · 最大流、最小割与建模归约 / Dinic：分层图与阻塞流 待审核 4 / 13
Dinic · 层次图 · 阻塞流

Dinic：分层图与阻塞流

Edmonds-Karp 每轮做一次完整的 BFS，却只从中拿走一条增广路就丢弃。BFS 已经把「s 到每个点的最短距离」全算了出来——这份全局层次信息本可以一次喂养出许多条增广路，EK 却每次重头来过，白白浪费。Dinic 算法（也写作 Dinitz）正是把这份信息榨干：它以相位 (phase) 为单位推进，每个相位先 BFS 建一张层次图 (level graph)，再在这张层次图上用一次 DFS 推出阻塞流 (blocking flow)，把当前层次下所有最短增广路一次性灌满，然后才重新 BFS、进入下一相位。

1 · 层次图：把残量网络削成「只许前进一层」

一个相位的第一步，是在当前残量网络上从源点 s 做一次 BFS，给每个点算出层号：

层号 (level) level[v]: 残量网络里从 s 到 v 的最短路边数（只数还有残量的边）。level[s] = 0；不可达的点没有层号。

层次图 (level graph): 在残量网络里只保留满足 level[v] = level[u] + 1 的残量边——也就是「严格往下一层走」的边。横跨同层、回退到上层、或一次跳两层的边一律剔除。

层次图是一张有向无环图 (DAG)：每条边都把层号 +1，不可能形成环。因此在它上面找 s→ts\to t 的路，天然就是当前残量网络里的最短增广路，且沿途不会走回头路。本页示例网经 BFS 后的层次如下（下方 lab 会随单步实时重算）：

L0 L1 L2 L3
s a, b c, d t

和 EK 的关键差别：EK 也用 BFS，但每次 BFS 只回溯一条路就推流、然后整张 BFS 信息作废。Dinic 把这张分层结果留下来，接着在它上面尽可能多地推流，直到这张层次图里再也榨不出 s→ts\to t 的路为止。

2 · 阻塞流与当前弧优化

在固定的层次图上，Dinic 要推的不是一条增广路，而是一个阻塞流:

阻塞流 (blocking flow): 一个在当前层次图上合法的流，使得每一条 s→ts\to t 路都至少含有一条饱和边（残量为 0）。换句话说：在这张层次图里，你再也找不到一条全程畅通的 s→ts\to t 路。

注意「阻塞」不等于「最大」：阻塞流只保证这张层次图被堵死，残量网络里可能还有更长的增广路——那些就留给下一个相位（重新 BFS 后层次会变，新边才会进入层次图）。推阻塞流的办法是在层次图上反复做 DFS：每找到一条 s→ts\to t 的下行路就推满它的瓶颈，直到 DFS 从 s 出发再也到不了 t。

当前弧优化 (current arc): 朴素 DFS 会反复从每个点的第一条边重新试探，退化得很慢。Dinic 给每个点 u 配一个指针 it[u]，记住「这个点的边已经试到第几条」。一旦某条边 u→vu\to v 被发现走不通（从 v 再也推不出流），指针就永久跳过它，本相位内不再回看。这样每条边在一个相位里只被「彻底尝试」常数次，把单相位推阻塞流的代价压到 O(VE)。

指针为何能安全跳过？因为在固定层次图(DAG)里，一条边一旦在某次 DFS 中被判定「下游无法再吸纳流量」，在本相位内这一判断不会翻案——层次不变，下游的容量只会越用越少，不会凭空多出来。所以这条边可以放心废弃。

3 · 单步运行 Dinic（两个相位）

这张网的最大流是 4,Dinic 正好用两个相位跑完。请重点看相位之间的对比：

  • 相位一 BFS 把 d 放在 L2,t 在 L3。层次图上推出两条长度 3 的最短路 s→a→c→ts\to a\to c\to t、s→b→d→ts\to b\to d\to t，总流量到 2；此时这张层次图被堵死（阻塞流完成）。
  • 相位二 重新 BFS，层次变了:d 从 L2 退到 L3、t 到 L4。于是交叉边 c→dc\to d 终于满足「层号 +1」进入层次图，更长的增广路 s→a→c→d→ts\to a\to c\to d\to t 把流补到 4。

这就是 Dinic 的精髓：重分层让更长的增广路登场——这正是 EK 每轮丢弃信息所错过的红利。

结束条件： 某个相位开头的 BFS 到不了汇点 t——残量网络里的层次图已断开，再也没有 s→ts\to t 路。此时流值就是最大流。和前面两页一样，末态从源点在残量网络中仍可达的点集 S（绿）与其余点之间的边（红）恰好是一个最小割，割容量 = 最大流（见 最小割）。

4 · 复杂度：为什么是 O(V²E)

Dinic 的复杂度由两部分相乘：相位数 × 单相位代价。

相位数 ≤ V − 1。 每经过一个相位，残量网络里 s→ts\to t 的最短路长度严格增加至少 1（本页示例：相位一 t 在 L3，相位二 t 在 L4）。最短路长度从 1 到最多 V−1V-1，所以最多 V−1V-1 个相位。

单相位 O(VE)。 借助当前弧优化，一个相位里每条边只被「彻底尝试」常数次；推出一条阻塞路最长 O(V)O(V)，推路次数与边数同阶，合计 O(VE)O(VE)。

总计 O(V²E)。 相乘即得——对一般图，这已远胜 Edmonds-Karp 的 O(VE2)O(VE^2)。

特殊网更快。 在单位容量网络（所有 cap = 1）上，Dinic 退化到 O(E√V)；二分图最大匹配正是这种网络，此时 Dinic 等价于 Hopcroft-Karp 算法（见 二分图匹配）。对单位容量的有向图，相位数还能进一步收紧到 O(E)O(\sqrt E)。

工程上，Dinic 实现简单、常数小、对绝大多数实际网络远快于最坏界，因此是默认首选的最大流算法之一。沿增广路这条路线还能再走一步：ISAP 把「每相位一次 BFS」压成全程一次，走不通时就地抬高标号。更激进的 push-relabel（预流推进）在某些稠密图上更快——它换了另一套范式，下面单步看它怎么跑。

5 · 进阶：另一套范式——push-relabel（预流推进）

到此为止（朴素 / EK / Dinic）都属于增广路框架：每轮找一条完整的 s→ts\to t 路再推流。push-relabel 彻底换思路——不找整条路，只看每个点的局部状态：

给每个点维护两个量：高度 h 和 超额 e（流入减流出，允许暂时 > 0，这种「不守恒的流」就叫预流 preflow）。先把源点抬到 h[s]=n、并把它所有出边一次灌满（制造一批超额）；随后反复对任意活跃点（e>0 且非源汇）做两种局部操作:

  • push：存在可行边 u→vu\to v（残量 > 0 且 h[u]=h[v]+1）→ 顺着它把超额往低处推；
  • relabel：有超额却没有可行下推边 → 把 h[u]h[u] 抬高到「最低可达邻居高度 + 1」，好让它下一步能推。

直觉就是水往低处流，推不动就把当前点垫高。当再没有活跃点时，预流自动变成一个合法的最大流。

节点上方 h= 是高度，下方 e= 是超额（橙色 = 仍活跃）;橙色描边 = 本步选中的活跃点；高亮边 = 本步 push 的边（橙 = 走反向边、撤销原流量）。

和 Dinic 的根本差别。 增广路算法是全局的：每步都要一条贯穿 s→ts\to t 的路。push-relabel 是局部的：每步只动一个点和它的一条边，靠 h 这个「势能」保证流量整体往汇点走、推不动的回流到源点。正因为操作局部、易并行，它在稠密图与并行 / 分布式实现里常胜过 Dinic；代价是高度、选点规则(FIFO / highest-label / excess-scaling)调起来更费心，直觉也不如增广路顺。

本节这版实现只定了选点规则，高度初值全取 0、判死时机全交给 relabel 自己爬。HLPP 在同一骨架上补两处工程优化（反向 BFS 定初始高度、gap 整批判死），在那一页的搁浅网上把 40 步压到 11 步。