跳至主要內容

Flow(网络流)

badbottle2026/3/31大约 5 分钟算法图论

网络流(Flow)

网络（network）是指一个特殊的有向图 𝐺 =(𝑉,𝐸)，其与一般有向图的不同之处在于有容量和源汇点．

  • 𝐸 中的每条边 (𝑢,𝑣) 都有一个被称为容量（capacity）的权值，记作 𝑐(𝑢,𝑣)．当 (𝑢,𝑣) ∉𝐸 时，可以假定 𝑐(𝑢,𝑣) =0．
  • 𝑉 中有两个特殊的点：源点（source）𝑠 和汇点（sink）𝑡（𝑠 ≠𝑡）．

对于网络 𝐺 =(𝑉,𝐸)，流（flow）是一个从边集 𝐸 到整数集或实数集的函数，其满足以下性质．

使用场景

包括但不限于： 最大流问题：对于网络 𝐺 =(𝑉,𝐸)，给每条边指定流量，得到合适的流 𝑓，使得 𝑓 的流量尽可能大．此时我们称 𝑓 是 𝐺 的最大流． 最小割问题：对于网络 𝐺 =(𝑉,𝐸)，找到合适的 𝑠-𝑡 割 {𝑆,𝑇}，使得 {𝑆,𝑇} 的总容量尽可能小．此时我们称 {𝑆,𝑇} 的总容量是 𝐺 的最小割． 最小费用最大流问题：在网络 𝐺 =(𝑉,𝐸) 上，对每条边给定一个权值 𝑤(𝑢,𝑣)，称为费用（cost），含义是单位流量通过 (𝑢,𝑣) 所花费的代价．对于 𝐺 所有可能的最大流，我们称其中总费用最小的一者为最小费用最大流．

最大流(max-flow)

模板

https://github.com/badb0ttle/iomanip/blob/main/MaxFlow.cpp

概述

令 𝐺 =(𝑉,𝐸) 是一个有源汇点的网络，我们希望在 𝐺 上指定合适的流 𝑓，以最大化整个网络的流量 |𝑓|（即 ∑𝑥∈𝑉𝑓(𝑠,𝑥) −∑𝑥∈𝑉𝑓(𝑥,𝑠)），这一问题被称作最大流问题（Maximum flow problem）．

福特-富尔克森增广

对于每条边 (𝑢,𝑣)，我们都新建一条反向边 (𝑣,𝑢)．我们约定 𝑓(𝑢,𝑣) = −𝑓(𝑣,𝑢)，这一性质可以通过在每次增广时引入退流操作来保证，即 𝑓(𝑢,𝑣) 增加时 𝑓(𝑣,𝑢) 应当减少同等的量． 对于当前流 𝑓，我们定义边 (𝑢,𝑣) 的剩余容量（residual capacity）为

𝑐f(𝑢,𝑣)=𝑐(𝑢,𝑣)−𝑓(𝑢,𝑣).𝑐_f(𝑢,𝑣)=𝑐(𝑢,𝑣)-𝑓(𝑢,𝑣).

若 𝑐_f(𝑢,𝑣) > 0，则说明在当前状态下这条边仍然允许继续送流；所有满足剩余容量大于 0 的边构成的图称为剩余网络（residual network）．

如果在剩余网络中存在一条从源点 𝑠 到汇点 𝑡 的路径，那么这条路径就称为增广路（augmenting path）．设这条路径上的最小剩余容量为

Δ=min⁡(𝑢,𝑣)∈P𝑐f(𝑢,𝑣),\Delta=\min_{(𝑢,𝑣)\in P} 𝑐_f(𝑢,𝑣),

则我们就可以沿着路径 𝑃 增加 \Delta 的流量，而不会违反任意边的容量限制．这一步操作称为一次增广．

增广时：

  • 若经过的是原图中的正向边 (𝑢,𝑣)，则令 𝑓(𝑢,𝑣) += \Delta；
  • 若经过的是反向边 (𝑣,𝑢)，则相当于撤销原来在 (𝑢,𝑣) 上的一部分流量，即令 𝑓(𝑢,𝑣) -= \Delta．

这样做有两个好处：

  • 可以在后续过程中“后悔”，把原来走错的流量退回来重新分配；
  • 每次增广后，流量依旧满足容量限制和流量守恒．

于是 Ford-Fulkerson 算法的流程就很自然：

  1. 初始时令所有边流量为 0．
  2. 在剩余网络中寻找一条 𝑠 到 𝑡 的增广路．
  3. 计算这条路径上的瓶颈容量 \Delta，并沿路径增广 \Delta．
  4. 重复上述过程，直到不存在增广路为止．

当不存在增广路时，当前流就是最大流．其直观理解是：源点已经无法再通过任何“还有余量”的路径把更多流送到汇点，因此流量不能继续增大．这一结论正是最大流最小割定理的基础．

需要注意的是，Ford-Fulkerson 只规定了“反复找增广路”这一思想，并没有规定具体怎样找路：

  • 若每次用 BFS 在剩余网络中找最短增广路，就得到 Edmonds-Karp 算法；
  • 若通过分层图和当前弧优化批量增广，就得到 Dinic 算法．

在竞赛与工程中，通常更常用 Edmonds-Karp 或 Dinic，因为它们的复杂度分析更稳定，也更容易保证不会退化得太严重．

Dinic

Dinic 算法可以看作对 Ford-Fulkerson 增广思想的进一步优化．它的核心在于：

  • 先用 BFS 在剩余网络上建立分层图；
  • 再只沿着满足层次递增的边进行 DFS 增广；
  • 配合当前弧优化，避免重复扫描已经无效的边．

其中，分层图指的是从源点 𝑠 出发按最短路层数划分点集后得到的图．若点 𝑣 在 BFS 中的层数记为 dep[𝑣]，那么只有满足

dep[𝑣]=dep[𝑢]+1dep[𝑣]=dep[𝑢]+1

的边 (𝑢,𝑣) 才会被保留在分层图中．这样做的意义是：每次增广都只会沿着“更靠近汇点”的方向前进，不会在同一层或更低层之间来回绕路．

Dinic 的一轮流程如下：

  1. 用 BFS 判断汇点 𝑡 是否还能从源点 𝑠 到达，同时求出每个点的层数；
  2. 若 𝑡 不可达，则说明不存在增广路，算法结束；
  3. 若 𝑡 可达，则在分层图上不断 DFS，尽可能多地增广，直到这一层图中再也无法送出新的流量；
  4. 重新 BFS 建立新的分层图，继续重复上述过程．

这里“在同一张分层图上不断 DFS 直到无法增广”为止，得到的流称为阻塞流（blocking flow）．求出阻塞流后，当前这张分层图就失效了，必须重新分层．

为了提升效率，Dinic 一般会加入当前弧优化．也就是对每个点记录一个当前扫描到哪一条出边的指针 cur[u]，这样当某条边已经被证实不能继续增广时，后续 DFS 就不用再从头枚举它之前的边了．这一优化在实际表现中非常重要．

Dinic 的时间复杂度通常写作 O(V2E)O(V^2E)．在二分图最大匹配等特殊图上，它还可以做到更优复杂度，因此它是竞赛中最常用的最大流算法之一．

网络流
版权归badb0ttle所有