网络最大流

最大流问题在边容量限制下，求从源点到汇点能够输送的最大净流量。

流与合法流

流网络是带容量的有向图；流是在这些边上分配的实际流量。整张图中有一个特别的起点 $s$ 和一个特别的终点 $t$，所有流量都从 $s$ 出发，最终希望汇聚到 $t$。

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

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

  $$0 \leqslant f(u,v) \leqslant c(u,v).$$

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

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

源点可以有入边，汇点也可以有出边。流的值定义为源点的净流出量，它由守恒条件等于汇点的净流入量；以下将不存在的边上流量视为 0：

$$|f| = \sum_v f(s,v)-\sum_v f(v,s).$$

最大流问题的目标，就是在所有合法流中找到一个使 $|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$ 的路径时，当前流就是最大流。

当残量图中没有增广路时，令 $S$ 为从源点仍可到达的顶点集合，$T=V\setminus S$。所有原图中从 $S$ 到 $T$ 的边都已饱和，否则还能到达 $T$；从 $T$ 到 $S$ 的边流量均为零，否则其反向残量边也能跨出 $S$。由流量守恒，净流量恰等于这个割的容量。流与割达到同一个值，结合任意流不超过任意割的上界，即得最大流最小割定理。

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

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

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

整数容量下，每次增广至少增加 1 单位流量，因而朴素方法会终止，但次数可能依赖流量的数值大小。任意实数容量配合任意选路规则可能不终止；选择路径的规则因此影响正确终止与复杂度保证。

Edmonds–Karp 算法

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

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

这样做的好处是，BFS 找到的路径长度可以帮助我们控制增广的次数，从而保证整体复杂度。理论上，Edmonds–Karp 的时间复杂度是 $O(VE^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$ 不可达为止。这样得到的最终流就是最大流。DFS 还应维护当前弧指针，记录每个顶点已尝试到哪条出边，避免重复扫描已无法推进的边。采用这一实现的通用时间界为 $O(V^2E)$。

例题

• 洛谷 P3376 网络最大流

延伸阅读

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