网络最大流

在管道网络、物流系统中，经常需要求解满足各个通路容量流量限制下，能从起点往终点运送多少东西。这就是最大流问题，要回答的限制下，从源头把尽可能多的流送到终点的最大流量和方案。

流与合法流

直观地说，流是一个带权有向图，边的权重就是这条边最多能通过多少流。整张图中有一个特别的起点 $s$ 和一个特别的终点 $t$，所有流量都从 $s$ 出发，最终希望汇聚到 $t$。

形式化地，一个流网络是带权有向图 $G=(V,E)$，其中每条有向边 $(u,v)$ 具有一个非负容量 $c(u,v)⩾0$，表示从 $u$ 到 $v$ 能通过的最大流量。我们在每条边上再指定一个实际流量 $f(u,v)$，得到一组流量分配。这组分配要满足两类约束，才称得上是一个合法流。

• 第一类是容量约束。对任意边 $(u,v)$，实际流量不能为负，也不能超过容量：

  $$0⩽f(u,v)⩽c(u,v).$$

• 第二类是流量守恒。对除 $s,t$ 以外的任意顶点 $v$，流入它的总流量等于流出它的总流量，也就是

  $$\sum _{u\in V}f(u,v)=\sum _{w\in V}f(v,w).$$

在这两个条件下，源点 $s$ 只“产生”流量，汇点 $t$ 只“吸收”流量。整个网络的总流量可以定义为源点的净流出量：

$$|f|=\sum _{v}f(s,v).$$

最大流问题的目标，就是在所有合法流中找到一个使 $|f|$ 尽可能大的流。

割与瓶颈

在直觉上，一个网络的能量输出往往受最细的那几根管子限制。为了刻画这种“瓶颈”，我们引入割的概念。

可以把割想象成在图上画出一条“切割线”，把 $s$ 所在的一边和 $t$ 所在的一边分开。所有从左边通向右边的边都被这道切割线切断，它们承载的容量总和，就是这道“瓶颈”的最大通过能力。

形式化的说，设 $V$ 是所有顶点的集合。我们把顶点分成两部分 $S$ 和 $T$，要求 $S\cup T=V$、$S\cap T=\varnothing$，并且源点 $s$ 在 $S$ 中，汇点 $t$ 在 $T$ 中。这种划分就叫做一个从 $s$ 到 $t$ 的割 $(S,T)$。

割的容量定义为所有从 $S$ 指向 $T$ 的边的容量之和：

$$c(S,T)=\sum _{u\in S,v\in T}c(u,v).$$

有一个简单但重要的事实：任意合法流的流量都不会超过任意一个割的容量。因为所有从 $s$ 出发最终流向 $t$ 的流量，必然要通过某条从 $S$ 到 $T$ 的边，自然受到这些边容量之和的限制。

最大流最小割定理

最大流最小割定理指出：

在一个流网络中，最大的可行流量等于最小的 $s-t$ 割的容量。

换句话说，从上界的角度看，任何一个割都给出了流量的上限；从算法的角度看，最大流算法会不断尝试增加流量，直到再也找不到新的“通路”为止，这时它刚好达到了某个割的容量上界。于是，全图中最紧的那个瓶颈，恰好决定了最大流的大小。

总而言之，流量受全局瓶颈限制，而增广型的算法做的就是一步步把流量顶到这个瓶颈上。

增广路框架：Ford–Fulkerson

求最大流最经典的思路是增广路（augmenting path）。可以这样理解：一开始所有边上流量为 0，此时显然是一个合法流。此后，只要还能在网络中找到一条从 $s$ 到 $t$ 的可用路径，就沿着这条路径再多送一点流，直到某条边的容量被用满。不断重复这个过程，网络中的流量就会逐步增长。

为了描述“还能多送多少”，我们在当前流的基础上构造一张残量网络（residual graph）。对于每条边 $(u,v)$，如果还没用满容量，就在残量网络中保留一条从 $u$ 到 $v$ 的边，剩余容量为 $c(u,v)-f(u,v)$。同时，如果当前在 $(u,v)$ 上已经有了流量 $f(u,v)$，那么我们允许在残量网络中从 $v$ 走回 $u$，容量为 $f(u,v)$，表示可以“回退”已经送出的那部分流量。

在残量网络上，从 $s$ 到 $t$ 的一条路径就叫做一条增广路。沿着这条路径，把流量增加到所有边都不超容量的最大幅度，就得到了一个新的合法流。只要还能找出新的增广路，就继续这个过程；当残量网络中再也找不到从 $s$ 到 $t$ 的路径时，当前流就是最大流。

这个方法的核心是把“能不能再多送一点流”转化成“还能不能在残量网络里找到一条路”。不同的最大流算法，区别主要在于如何在残量网络中找路径、以及怎样组织多次增广。

这一整套框架通常被统称为 Ford–Fulkerson 方法。用伪代码可以简要写成：

初始化所有流量 f(u,v) = 0
while 在残量网络中存在 s 到 t 的路径 P:
  找出 P 上所有边的残量最小值 Δ
  沿 P 上的边增加流量 Δ
  更新正向边与反向边的残量

Edmonds–Karp 算法

Edmonds–Karp 是 Ford–Fulkerson 的一个具体实现，它在残量网络中总是用 BFS 找“边数最少”的增广路。也就是说，每次增广都沿着当前残量图中从 $s$ 到 $t$ 的最短路径（按边数）来送流。

算法的框架与前面一样：先在残量图上用 BFS 找一条从 $s$ 到 $t$ 的路径。如果找不到，说明已经没有增广路，当前流就已经是最大流；如果找到了，就按这条路上的最小残量 $\mathrm{\Delta }$ 来增广，然后更新残量图，继续下一轮。

这样做的好处是，BFS 找到的路径长度可以帮助我们控制增广的次数，从而保证整体复杂度。理论上，Edmonds–Karp 的时间复杂度是 $O(V{E}^2)$，在点数和边数不是特别大的情况下，一般可以接受。

整体流程可以概括为：

def max_flow_EK():
  初始化 f = 0
  while True:
    用 BFS 在残量网络中找 s 到 t 的路径 P
    if 不存在路径:
      break
    Δ = P 上边的残量最小值
    沿 P 更新流量和残量
  返回当前流量 |f|

Dinic 算法

Dinic 算法可以看作对增广路思想的进一步组织和优化，是竞赛中常用的最大流算法之一。

Dinic 的第一步是构造一张分层图。在当前残量网络中，从源点 $s$ 做一遍 BFS，计算每个点到 $s$ 的最短距离（按边数），记作 dist。然后我们只保留那些满足 dist[v] = dist[u] + 1 的边，得到一张只允许“沿着层次向前走”的新图。如果在这张图里汇点 $t$ 不可达，那么说明已经不存在任何增广路，当前流就是最大流。

在分层图上，Dinic 第二步是寻找一个阻塞流。做法是：用 DFS 沿着层次递增的边不断从 $s$ 走到 $t$，每找到一条路径就尽可能增广；当某条边容量耗尽时，就不再沿这条边尝试。经过足够多次 DFS，当分层图中再也找不到通往 $t$ 的路径时，我们就说在当前分层图里找到了一个阻塞流。

算法整体上就是反复执行“构造分层图、在分层图内找到阻塞流”这两个步骤，直到分层图中 $t$ 不可达为止。这样得到的最终流就是最大流。理论分析表明，其复杂度是 $O(E{V}^2)$。

例题

• 洛谷 P3376 网络最大流

延伸阅读

• 如何使最大流的 Dinic 算法达到理论上的最坏时间复杂度？ - 知乎