网络流与二分匹配

网络流理论是组合优化中最富有魅力的分支之一。它将现实世界中”物流在管道中流动”这一直觉，抽象为精确的数学模型，并在此基础上导出了一系列深刻的对偶定理和高效算法。从航线调度到图像分割，从棒球淘汰赛判定到编译器寄存器分配，网络流的应用远比多数人想象的广泛。

本文将从最大流问题的形式化定义出发，逐步展开 Ford-Fulkerson 方法、Edmonds-Karp 算法、 Dinic 算法，然后过渡到最大流最小割定理的证明，再进入二分匹配的世界—— 包括通过最大流归约、匈牙利算法和 Hopcroft-Karp 算法。最后我们讨论最小费用最大流、真实工程案例，以及一份完整的 Dinic 算法 C 语言实现。

一、最大流问题的形式化定义

流网络

一个流网络（flow network）是一个有向图 G = (V, E)，其中：

存在唯一的源点 s 和汇点 t；
每条边 (u, v) 具有非负容量 c(u, v) >= 0；
若 (u, v) 不属于 E，则 c(u, v) = 0。

可行流

一个可行流（feasible flow）是函数 f: V x V -> R，满足以下两个约束：

容量约束：对所有 u, v，有 0 <= f(u, v) <= c(u, v)。
流量守恒：对所有 u（u 不为 s 和 t），流入等于流出：

sum_{v} f(v, u) = sum_{v} f(u, v)

流值

流的值（value）定义为从源点净流出的总量：

|f| = sum_{v} f(s, v) - sum_{v} f(v, s)

最大流问题：在满足容量约束和流量守恒的前提下，求使 |f| 最大的可行流。

线性规划视角

最大流问题可以自然地表述为一个线性规划（LP）：

maximize    sum_{v} f(s,v)
subject to  f(u,v) <= c(u,v)       对所有边 (u,v)
            f(u,v) >= 0             对所有边 (u,v)
            sum_v f(v,u) = sum_v f(u,v)  对所有 u != s, t

这个 LP 的对偶恰好给出最小割问题——我们稍后在第五节证明这一点。

二、Ford-Fulkerson 方法与增广路径

残量网络

给定流 f，残量网络 G_f = (V, E_f) 定义如下：

若 f(u, v) < c(u, v)，则 E_f 包含前向边 (u, v)，残量为 c_f(u, v) = c(u, v) - f(u, v)；
若 f(u, v) > 0，则 E_f 包含反向边 (v, u)，残量为 c_f(v, u) = f(u, v)。

残量网络的核心思想是：前向边表示”还能再推多少”，反向边表示”已经推了多少可以撤回”。

增广路径

在残量网络 G_f 中从 s 到 t 的任意路径称为增广路径（augmenting path）。沿增广路径能推送的最大流量为路径上所有边残量的最小值——这就是该路径的瓶颈容量。

算法框架

Ford-Fulkerson(G, s, t):
    初始化 f(u,v) = 0  对所有 (u,v)
    while 残量网络 G_f 中存在从 s 到 t 的增广路径 p:
        delta = min{ c_f(u,v) : (u,v) in p }
        对 p 上每条边 (u,v):
            if (u,v) 是前向边:
                f(u,v) += delta
            else:
                f(v,u) -= delta
    return f

终止性与复杂度

当所有容量为整数时，每次增广至少增加 1 单位流值，因此算法在 O(|f| E) 时间内终止，其中 |f*| 是最大流的值。
当容量为无理数时，Ford-Fulkerson 可能不终止——Zwick 于 1995 年给出了具体的构造。
当容量为有理数时，算法一定终止，但可能需要指数级步数。

一个经典陷阱

考虑如下简单图：s -> a, s -> b, a -> b, a -> t, b -> t，其中 s->a 容量 1000，s->b 容量 1000，a->b 容量 1，a->t 容量 1000，b->t 容量 1000。

如果选择增广路径的策略不当（每次都经过 a->b 那条容量为 1 的边），则需要 2000 次增广才能找到最大流 2000。这说明 Ford-Fulkerson 的效率严重依赖增广路径的选择策略。

三、Edmonds-Karp 算法：BFS 增广

核心改进

Edmonds 和 Karp（1972）提出了一个简单而深刻的改进： 每次选择残量网络中最短的增广路径——即用 BFS 寻找增广路径。

时间复杂度

Edmonds-Karp 算法的时间复杂度为 O(V * E^2)，与最大流值无关。

证明关键引理：

距离单调性：设 d_f(v) 为残量网络 G_f 中 s 到 v 的 BFS 距离。每次增广后，对所有 v 有 d_{f’}(v) >= d_f(v)。
增广次数上界：每条边至多成为 O(V) 次增广的瓶颈边。因为边 (u, v) 成为瓶颈边后被删除，要重新出现需要反向边 (v, u) 被使用，此时 d(u) 至少增加 2。由于距离至多为 V，每条边至多贡献 O(V) 次瓶颈。
边数为 E，故总增广次数为 O(V * E)。每次 BFS 为 O(E)，总计 O(V * E^2)。

伪代码

Edmonds-Karp(G, s, t):
    初始化 f(u,v) = 0
    while true:
        // BFS 寻找最短增广路径
        parent = BFS(G_f, s, t)
        if t 不可达:
            break
        // 计算瓶颈
        delta = INF
        v = t
        while v != s:
            u = parent[v]
            delta = min(delta, c_f(u, v))
            v = u
        // 更新流
        v = t
        while v != s:
            u = parent[v]
            f(u,v) += delta
            f(v,u) -= delta
            v = u
    return f

实践表现

虽然 O(V * E^2) 看起来不够快，Edmonds-Karp 在随机图和稀疏图上的表现往往远好于最坏情况。对于竞赛中的小规模问题（V <= 500，E <= 5000），Edmonds-Karp 通常足够。

四、Dinic 算法：分层图与阻塞流

Dinic（1970）提出的算法是实践中最常用的最大流算法之一，其核心思想是分层图（layered graph）和阻塞流（blocking flow）。

分层图的构造

对残量网络 G_f 做一次 BFS，计算每个节点到源点的距离 d(v)。 分层图 L_f 只保留满足 d(v) = d(u) + 1 的边 (u, v)——即只保留”沿最短路方向前进”的边。

下图展示了一个分层图的结构：

图中节点按 BFS 距离分成四层（d=0, 1, 2, 3），边只从低层指向高层。紫色虚线表示反向边，它们不属于分层图但存在于残量网络中。

阻塞流

在分层图 L_f 中，一个流 g 是阻塞流，当且仅当 L_f 中从 s 到 t 的每条路径至少有一条边被 g 饱和（残量为 0）。

注意：阻塞流不一定是分层图中的最大流——它只要求阻断所有 s-t 路径即可。

算法流程

Dinic(G, s, t):
    初始化 f = 0
    while true:
        对 G_f 做 BFS，构造分层图 L_f
        if t 在 L_f 中不可达:
            break
        在 L_f 中找到一个阻塞流 g
        f = f + g    // 将阻塞流累加到总流
    return f

阻塞流的求解：DFS + 当前弧优化

在分层图上用 DFS 寻找阻塞流。关键优化是当前弧（current arc）技巧：

对每个节点 u，维护一个指针 cur[u]，指向 u 的邻接表中下一条待探索的边。
当沿 DFS 走到死路（无法到达 t）时，回退并推进当前弧指针。
每条边至多被访问两次（一次前进、一次回退），因此单次阻塞流的时间为 O(V * E)。

时间复杂度分析

定理：Dinic 算法的时间复杂度为 O(V^2 * E)。

证明：

每次 BFS 阶段后，分层图的层数（即 d(t)）严格递增。因为阻塞流已阻断所有长度为 d(t) 的增广路径，下一轮 BFS 中 d(t) 至少增加 1。
d(t) 至多为 V - 1，故 BFS 阶段至多执行 V - 1 次。
每个阶段中，阻塞流的计算需要 O(V * E) 时间。
总计 O(V * (V * E)) = O(V^2 * E)。

单位容量图上的特殊复杂度

当所有边容量为 1 时，Dinic 算法的复杂度降为 O(E * sqrt(V))。这是因为：

每个阶段的阻塞流计算只需 O(E) 时间（每条边至多使用一次）。
在 O(sqrt(V)) 个阶段后，剩余增广路径长度超过 sqrt(V)，而此时最多还有 O(sqrt(V)) 单位流值可增广。

这个性质使 Dinic 算法在二分匹配问题上能达到 O(E * sqrt(V))—— 与 Hopcroft-Karp 算法的复杂度相同。

五、最大流最小割定理

割的定义

给定流网络 G = (V, E)，一个 s-t 割（cut）是将 V 划分为 S 和 T = V S 的方式，使得 s 属于 S，t 属于 T。割的容量为：

c(S, T) = sum_{u in S, v in T} c(u, v)

最小割问题：找使 c(S, T) 最小的 s-t 割。

定理陈述

最大流最小割定理（Ford & Fulkerson, 1956）：

在任何流网络中，最大流的值等于最小割的容量。

这是组合优化中最深刻的对偶定理之一。

弱对偶性（容易的方向）

对于任意可行流 f 和任意 s-t 割 (S, T)：

|f| = sum_{u in S, v in T} f(u,v) - sum_{u in T, v in S} f(u,v)
     <= sum_{u in S, v in T} f(u,v)
     <= sum_{u in S, v in T} c(u,v)
     = c(S, T)

因此：最大流值 <= 最小割容量。这是弱对偶性。

强对偶性（通过 Ford-Fulkerson 终止条件）

当 Ford-Fulkerson 算法终止时，残量网络中不存在从 s 到 t 的路径。令 S = { v : v 在 G_f 中从 s 可达 }，T = V S。

由于 t 不在 S 中，(S, T) 是一个 s-t 割。对于此割：

对每条边 (u, v) 满足 u 属于 S，v 属于 T：残量 c(u,v) - f(u,v) = 0（否则 v 从 s 可达，矛盾），即 f(u,v) = c(u,v)。
对每条边 (v, u) 满足 v 属于 T，u 属于 S：残量 f(v,u) = 0（否则经反向边 v 从 s 可达，矛盾），即 f(v,u) = 0。

因此：

|f| = sum_{u in S, v in T} c(u,v) - 0 = c(S, T)

我们找到了一个流和一个割，使流值等于割容量。结合弱对偶性，这个流就是最大流，这个割就是最小割。

LP 对偶视角

最大流的 LP 对偶可以写成：

minimize    sum_{(u,v) in E} c(u,v) * d(u,v)
subject to  d(u,v) - p(u) + p(v) >= 0   对所有边 (u,v)
            p(s) - p(t) >= 1
            d(u,v) >= 0

其中 p(v) 是节点的”势”变量，d(u,v) 是边的变量。

当最优解中 p 只取 0/1 值时，{v : p(v) = 1} 恰好定义了一个最小割。 LP 强对偶定理保证最优值相等，这给出了最大流最小割定理的另一个证明。

这个对偶视角的美妙之处在于：它把一个组合优化定理（最大流 = 最小割）还原为线性规划的一般性定理（LP 强对偶），揭示了问题的本质结构。

最小割的求解

最大流算法不仅给出最大流值，还自然地给出最小割：算法终止后，在残量网络中从 s 做一次 BFS/DFS，可达节点集合为 S，不可达节点集合为 T。 (S, T) 就是一个最小割。

六、二分匹配与最大流归约

二分图匹配问题

给定二分图 G = (L, R, E)，其中 L 和 R 是两个不相交的顶点集，E 的每条边连接 L 中的一个点和 R 中的一个点。匹配是 E 的子集 M，使得每个顶点至多被 M 中的一条边覆盖。 最大匹配是边数最多的匹配。

通过最大流求解

构造流网络：

添加源点 s 和汇点 t。
对每个 l 属于 L，添加边 (s, l)，容量为 1。
对每条二分图的边 (l, r)，添加边 (l, r)，容量为 1。
对每个 r 属于 R，添加边 (r, t)，容量为 1。

定理：此流网络的最大流值等于原二分图的最大匹配数。

证明：

匹配 -> 流：对匹配 M 中的每条边 (l, r)，令 f(s,l) = f(l,r) = f(r,t) = 1。这是一个值为 |M| 的可行流。
流 -> 匹配：由于所有容量为整数，存在整数最优流。取 M = { (l, r) : f(l, r) = 1 }。因为每个 l 的入流至多为 1，每个 r 的出流至多为 1， M 是一个合法匹配。

由于 Dinic 算法在单位容量图上的复杂度为 O(E * sqrt(V))，通过最大流求解二分匹配的时间复杂度为 O(E * sqrt(V))。

Hall 定理

Hall 定理（1935）：二分图 G = (L, R, E) 存在覆盖 L 的完美匹配的充要条件是：对 L 的任意子集 S，S 的邻居集 N(S) 满足 |N(S)| >= |S|。

Hall 定理可以由最大流最小割定理导出——这是网络流理论统一性的又一体现。

Konig 定理

Konig 定理（1931）：在二分图中，最大匹配数等于最小顶点覆盖数。

这是最大流最小割定理在二分图上的特殊情形：最大匹配对应最大流，最小顶点覆盖对应最小割。

七、匈牙利算法与加权匹配

匈牙利算法（Kuhn-Munkres）

匈牙利算法解决的是加权二分匹配问题：给定 n x n 的权重矩阵 W，找一个完美匹配使总权重最大（或最小）。

算法思想

算法维护一组顶标（potential）：对 L 中的每个点 u 有标签 lx[u]，对 R 中的每个点 v 有标签 ly[v]，满足：

lx[u] + ly[v] >= W[u][v]    对所有 u, v

定义相等子图：只包含满足 lx[u] + ly[v] = W[u][v] 的边。

关键性质：如果相等子图中存在完美匹配，则该匹配就是最优匹配。因为任何匹配 M 的权重满足：

sum_{(u,v) in M} W[u][v] <= sum_{u} lx[u] + sum_{v} ly[v]

而相等子图中的匹配恰好取等。

算法流程

Hungarian():
    // 初始化顶标
    lx[u] = max_v W[u][v]
    ly[v] = 0

    for 每个未匹配的 u in L:
        // 用 BFS 在相等子图中寻找增广路径
        if 找到增广路径:
            沿增广路径翻转匹配
        else:
            // 调整顶标，扩大相等子图
            delta = min{ lx[u] + ly[v] - W[u][v] :
                         u in 已访问的 L 节点,
                         v in 未访问的 R 节点 }
            对已访问的 L 节点: lx[u] -= delta
            对已访问的 R 节点: ly[v] += delta
            重新尝试增广

时间复杂度

朴素实现为 O(n^3)，使用 Dijkstra 风格的顶标调整可优化到 O(n^3)—— 但常数因子更小。对于 n <= 1000 的问题，匈牙利算法是首选。

与最小费用流的关系

加权二分匹配等价于最小费用最大流：在二分匹配的流网络中，将边权作为费用，容量保持为 1。匈牙利算法可以视为在这个特殊结构上的最小费用流算法的专门化版本。

八、Hopcroft-Karp 算法

动机

朴素的增广路径匹配算法（每次 DFS/BFS 找一条增广路径）的复杂度为 O(V * E)。 Hopcroft 和 Karp（1973）发现：同时沿所有最短增广路径增广可以大幅减少阶段数。

算法框架

Hopcroft-Karp(G):
    M = 空匹配
    while true:
        // 阶段 1：BFS 找所有最短增广路径的长度
        用 BFS 从所有未匹配的 L 节点出发，
        交替经过未匹配边和匹配边，
        直到到达某个未匹配的 R 节点。
        记录分层信息。

        if 无增广路径:
            break

        // 阶段 2：DFS 找极大组不相交的最短增广路径
        for 每个未匹配的 L 节点 u:
            DFS(u)  // 沿分层图寻找增广路径并翻转
    return M

时间复杂度

定理：Hopcroft-Karp 算法的时间复杂度为 O(sqrt(V) * E)。

证明思路：

每个阶段执行一次 BFS（O(E)）和若干次 DFS（总计 O(E)），故每个阶段 O(E)。
设当前匹配 M 的大小为 m，最大匹配大小为 m*。在第 k 个阶段后，最短增广路径长度至少为 2k + 1。
若当前最短增广路径长度为 l，则 m* - m <= V / l。因此当 l > sqrt(V) 时，剩余增广量不超过 sqrt(V)，每个阶段至少增广 1，故剩余阶段数不超过 sqrt(V)。
前 sqrt(V) 个阶段已执行，加上至多 sqrt(V) 个后续阶段，总阶段数为 O(sqrt(V))。
总时间 O(sqrt(V) * E)。

与 Dinic 的关系

在单位容量网络上运行 Dinic 算法，其行为与 Hopcroft-Karp 算法本质相同：

Dinic 的 BFS 分层对应 Hopcroft-Karp 的 BFS 阶段。
Dinic 的阻塞流对应 Hopcroft-Karp 的极大不相交增广路径集。
两者在单位容量图上都达到 O(E * sqrt(V))。

这并非巧合——Hopcroft-Karp 可以视为 Dinic 算法在二分匹配上的特殊化。

九、最小费用最大流

问题定义

在流网络的基础上，每条边 (u, v) 除了容量 c(u, v) 外，还有单位费用 w(u, v)。 最小费用最大流问题要求：在所有最大流中，找总费用最小的那个。

总费用 = sum_{(u,v)} f(u,v) * w(u,v)

连续最短路算法（SSP）

最小费用最大流的经典算法是连续最短路算法（Successive Shortest Path）：

SSP(G, s, t):
    f = 0
    while 残量网络 G_f 中存在从 s 到 t 的路径:
        在 G_f 中用最短路算法（以费用为边权）找 s 到 t 的最短路径 p
        沿 p 增广（增广量为路径上的最小残量）
        更新 f
    return f

处理负权边

残量网络中的反向边费用为 -w(u, v)，这意味着图中可能存在负权边。解决方案：

Bellman-Ford：直接处理负权边，单次 O(V * E)，总计 O(V^2 * E^2) 或 O(F * V * E)。
Johnson 技术：用势函数消除负权边，然后用 Dijkstra。先用一次 Bellman-Ford 计算势函数 h(v)，之后每次增广用 Dijkstra，单次 O(E log V)，总计 O(F * E log V) 或 O(V * E * log V) 取决于场景。

SPFA 加速

在实践中，SPFA（Shortest Path Faster Algorithm）常被用于最小费用流：它是 Bellman-Ford 的队列优化版本，平均复杂度通常远好于最坏情况。但需注意：SPFA 在特殊构造图上可能退化到 O(V * E)。

Primal-Dual 方法

对于更一般的最小费用流问题，Primal-Dual 方法同时维护原始变量（流）和对偶变量（势），通过对偶变量指导增广方向。这种方法在理论和实践中都很重要，它是匈牙利算法和网络单纯形法的统一框架。

应用场景

最小费用最大流广泛应用于：

运输问题：从多个仓库向多个客户运送货物，最小化运输成本。
任务分配：将 n 个任务分配给 n 个工人，最小化总成本。
网络设计：在满足流量需求的前提下，选择最经济的网络拓扑。

十、Dinic 算法的完整 C 实现

以下是 Dinic 算法的完整 C 语言实现，包含链式前向星存图、BFS 分层和 DFS 阻塞流。代码经过充分注释，可直接用于竞赛或工程项目。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

/*
 * Dinic 最大流算法
 *
 * 时间复杂度：O(V^2 * E)
 * 空间复杂度：O(V + E)
 *
 * 使用链式前向星（adjacency list with edge array）存图，
 * 正向边和反向边成对存储，便于残量网络维护。
 */

#define MAXN 10005
#define MAXM 200005
#define INF  0x3f3f3f3f

/* ---- 链式前向星 ---- */

struct Edge {
    int to;       /* 终点 */
    int cap;      /* 残量 */
    int next;     /* 同起点的下一条边 */
};

static struct Edge edges[MAXM * 2];
static int head[MAXN];
static int edge_cnt;

static void init_graph(int n)
{
    memset(head, -1, sizeof(int) * (n + 1));
    edge_cnt = 0;
}

/*
 * 添加一条从 u 到 v、容量为 cap 的边，
 * 同时添加容量为 0 的反向边。
 * 正向边编号为偶数，反向边编号为奇数——
 * 利用 XOR 1 可以快速定位配对边。
 */
static void add_edge(int u, int v, int cap)
{
    edges[edge_cnt].to   = v;
    edges[edge_cnt].cap  = cap;
    edges[edge_cnt].next = head[u];
    head[u] = edge_cnt++;

    edges[edge_cnt].to   = u;
    edges[edge_cnt].cap  = 0;     /* 反向边初始残量为 0 */
    edges[edge_cnt].next = head[v];
    head[v] = edge_cnt++;
}

/* ---- BFS 分层 ---- */

static int level[MAXN];
static int queue[MAXN];

/*
 * 在残量网络上做 BFS，计算每个节点到源点的层次。
 * 返回 1 表示汇点可达（存在增广路径），0 表示不可达。
 */
static int bfs(int s, int t, int n)
{
    memset(level, -1, sizeof(int) * (n + 1));
    int front = 0, back = 0;

    level[s] = 0;
    queue[back++] = s;

    while (front < back) {
        int u = queue[front++];
        for (int i = head[u]; i != -1; i = edges[i].next) {
            int v = edges[i].to;
            if (level[v] == -1 && edges[i].cap > 0) {
                level[v] = level[u] + 1;
                queue[back++] = v;
            }
        }
    }

    return level[t] != -1;
}

/* ---- DFS 寻找阻塞流 ---- */

static int cur[MAXN];   /* 当前弧优化 */

/*
 * 从 u 出发，在分层图上 DFS 推送最多 pushed 单位的流到汇点 t。
 * 返回实际推送的流量。
 *
 * cur[] 实现当前弧优化：已经探索过的死路不会再走，
 * 保证单次阻塞流的总时间为 O(VE)。
 */
static int dfs(int u, int t, int pushed)
{
    if (u == t)
        return pushed;

    for (int *i = &cur[u]; *i != -1; *i = edges[*i].next) {
        int e  = *i;
        int v  = edges[e].to;

        if (level[v] != level[u] + 1 || edges[e].cap <= 0)
            continue;

        int d = dfs(v, t, pushed < edges[e].cap ? pushed : edges[e].cap);

        if (d > 0) {
            edges[e].cap     -= d;   /* 正向边残量减少 */
            edges[e ^ 1].cap += d;   /* 反向边残量增加 */
            return d;
        }
    }

    return 0;
}

/* ---- Dinic 主函数 ---- */

/*
 * 求从 s 到 t 的最大流。
 * 调用前需先用 init_graph() 初始化，再用 add_edge() 添加所有边。
 */
static long long dinic(int s, int t, int n)
{
    long long max_flow = 0;

    while (bfs(s, t, n)) {
        /* 每轮 BFS 后重置当前弧 */
        memcpy(cur, head, sizeof(int) * (n + 1));

        int d;
        while ((d = dfs(s, t, INF)) > 0) {
            max_flow += d;
        }
    }

    return max_flow;
}

/* ---- 输入/输出与主函数 ---- */

/*
 * 输入格式：
 *   第一行：n m s t （节点数、边数、源点、汇点）
 *   接下来 m 行：u v cap （有向边 u->v，容量 cap）
 *
 * 输出格式：
 *   最大流值
 */
int main(void)
{
    int n, m, s, t;

    if (scanf("%d %d %d %d", &n, &m, &s, &t) != 4) {
        fprintf(stderr, "输入格式错误\n");
        return 1;
    }

    init_graph(n);

    for (int i = 0; i < m; i++) {
        int u, v, cap;
        if (scanf("%d %d %d", &u, &v, &cap) != 3) {
            fprintf(stderr, "边 %d 输入格式错误\n", i);
            return 1;
        }
        add_edge(u, v, cap);
    }

    printf("%lld\n", dinic(s, t, n));

    return 0;
}

/*
 * 使用示例：
 *
 * 输入（上图的网络）：
 *   7 10 1 7
 *   1 2 10
 *   1 3 8
 *   1 4 7
 *   2 5 6
 *   2 6 4
 *   3 5 5
 *   3 6 3
 *   4 6 7
 *   5 7 9
 *   6 7 12
 *
 * 输出：
 *   21
 *
 * 编译：gcc -O2 -o dinic dinic.c
 * 运行：./dinic < input.txt
 */

实现要点

链式前向星：用数组模拟邻接表，避免 malloc 开销。正向边和反向边成对存储，编号分别为 2k 和 2k+1，通过 XOR 1 即可找到配对边——这是竞赛中的经典技巧。
当前弧优化：cur[] 数组在每轮 BFS 后重置为 head[]， DFS 过程中只向前推进不回退。这保证每条边在一轮 DFS 中至多被检查常数次。
流量类型：主函数使用 long long 累加最大流值，防止溢出。 DFS 内部使用 int，因为单次增广量不会超过 INT_MAX（假设边容量在 int 范围内）。
静态数组：全局静态数组避免了动态内存分配，适合竞赛和嵌入式场景。实际工程中可改为动态分配。

十一、实际应用与工程经验

航线调度

航空公司需要用最少数量的飞机覆盖一组航班。每个航班有固定的起飞时间、降落时间和机场。如果航班 A 降落后，飞机有足够时间转场或直接执飞航班 B，则 A 和 B 之间可以衔接。

建模：构造二分图，左侧为航班的”出发端”，右侧为航班的”到达端”。若 A 可以衔接 B，则连边。最小飞机数 = 航班总数 - 最大匹配数。

图像分割

计算机视觉中的前景/背景分割可以建模为最小割问题：

每个像素是一个节点。
源点连接每个像素，边权为该像素属于前景的概率。
汇点连接每个像素，边权为该像素属于背景的概率。
相邻像素之间连边，边权反映颜色/纹理的相似度（平滑先验）。

最小割将像素分为两组，最小化分割的总代价。这就是 Boykov-Kolmogorov 算法的基础，广泛应用于医学影像和视频编辑。

棒球淘汰赛判定

给定棒球联赛的当前积分榜和剩余赛程，判断某支队伍是否已被淘汰（不可能夺冠）。这个看似简单的问题，其精确判定需要用到最大流：

对每对尚有比赛的队伍创建一个”比赛节点”。
源点连接每个比赛节点，容量为剩余比赛场次。
比赛节点连接对应的两支队伍，容量为无穷大。
每支队伍连接汇点，容量为目标队伍最多能赢的场次减去该队伍当前胜场数。

如果最大流等于所有剩余比赛的总场次，则目标队伍仍有机会；否则已被淘汰。

工程实践中的注意事项

问题	根因	解决方案
整数溢出	流值累加超出 int 范围	使用 long long 或 int64_t
重边处理	同一对节点间有多条边	链式前向星天然支持重边，无需合并
无向图建模	无向边等价于两条有向边	添加 (u,v) 和 (v,u) 各容量 c，但共享反向边时需注意
浮点容量	精度丢失导致死循环	乘以公倍数转为整数，或使用 epsilon 比较
超级源/汇	多源多汇问题	添加超级源 S 和超级汇 T，S 到每个源连无穷边，每个汇到 T 连无穷边
节点容量	节点有流量上限	拆点：将节点 v 拆为 v_in 和 v_out，中间连容量为上限的边
下界可行流	边有流量下界	转化为无下界问题：减去下界，修正源汇容量，添加辅助边
负环检测	最小费用流中出现负环	用 Bellman-Ford 检测，或使用势函数消除
稀疏 vs 稠密	算法选择不当	稀疏图用 Dinic，稠密图考虑 Push-Relabel
TLE 调试困难	不清楚瓶颈在哪	先确认图的规模和算法复杂度，再检查实现常数

算法选型指南

场景	推荐算法	复杂度
一般最大流（V <= 10^4）	Dinic	O(V^2 E)
稠密图最大流	Push-Relabel (HLPQ)	O(V^2 sqrt(E))
二分匹配（无权）	Hopcroft-Karp / Dinic	O(E sqrt(V))
二分匹配（带权）	匈牙利 / KM	O(V^3)
最小费用最大流	SPFA 增广 / Primal-Dual	O(VE * F) / O(VE log V * F)
最小割（图像分割）	Boykov-Kolmogorov	实践中远优于理论界

十二、个人思考与总结

网络流理论的美

网络流理论的美在于对偶性的无处不在：

最大流与最小割是对偶的。
最短增广路径与距离标号是对偶的。
匈牙利算法的顶标本质上是对偶变量。
甚至 Dinic 的分层图也可以理解为一种对偶结构。

理解网络流，关键不在于背诵某个算法的实现细节，而在于理解残量网络这一核心抽象。一旦你理解了”前向边表示剩余容量，反向边表示已推送流量”这一思想，所有最大流算法都只是在残量网络上寻找增广路径的不同策略。

学习路径建议

我建议的学习路径是：

先理解 Ford-Fulkerson 方法和残量网络的概念。
实现 Edmonds-Karp（BFS 增广），在小图上手动模拟。
学习 Dinic 算法，重点理解分层图和当前弧优化。
证明最大流最小割定理——这是检验你是否真正理解的试金石。
学习二分匹配的最大流归约。
如有需要，再学习最小费用流和匈牙利算法。

竞赛中的经验

在算法竞赛中，网络流题目的难点通常不在于实现算法本身，而在于建模——如何将问题转化为网络流问题。一些常见的建模技巧：

时间展开：将时间维度展开为多层图。
拆点：将节点约束转化为边约束。
二分答案 + 最大流验证：将优化问题转化为判定问题。
最小割模型：将”选择”问题转化为最小割。

我个人的体会是：写过十道网络流建模题后，你会对这类问题形成直觉。前三道可能完全没有思路，到第十道时你就能在十分钟内完成建模。这是一种需要练习才能获得的能力，光读理论是不够的。

工程中的考量

在工程项目中使用网络流算法时，需要注意：

数值稳定性：避免浮点容量，尽量用整数。如果必须使用浮点数，选择有理数算术或设置合适的 epsilon。
增量更新：当图发生小幅变化时，不必从头重新计算最大流。可以在原有流的基础上，只在变化的部分重新增广。
并行化：Push-Relabel 算法比 Dinic 更适合并行化，因为推送和重标号操作可以在不同节点上并行执行。
库的选择：大多数情况下不需要自己实现。 C++ 可以用 Lemon 库，Python 可以用 NetworkX，Java 可以用 JGraphT。

最后的话

网络流是我在算法学习过程中最享受的主题之一。它将图论、线性规划和组合优化串联在一起，展示了数学的统一性和力量。每当我在一个看似无关的问题中发现网络流的影子时，都会由衷地感叹这个理论的深远与优雅。

希望这篇文章能帮助你走进网络流的世界。如果你觉得某些部分不够清晰，欢迎回头多读几遍—— 网络流的核心概念并不多，但每一个都值得反复咀嚼。

参考文献

Ford, L. R., Fulkerson, D. R. (1956). “Maximal Flow through a Network.” Canadian Journal of Mathematics, 8, 399-404.
Edmonds, J., Karp, R. M. (1972). “Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems.” Journal of the ACM, 19(2), 248-264.
Dinic, E. A. (1970). “Algorithm for Solution of a Problem of Maximum Flow in Networks with Power Estimation.” Soviet Mathematics Doklady, 11, 1277-1280.
Hopcroft, J. E., Karp, R. M. (1973). “An n^{5/2} Algorithm for Maximum Matchings in Bipartite Graphs.” SIAM Journal on Computing, 2(4), 225-231.
Kuhn, H. W. (1955). “The Hungarian Method for the Assignment Problem.” Naval Research Logistics Quarterly, 2, 83-97.
Boykov, Y., Kolmogorov, V. (2004). “An Experimental Comparison of Min-Cut/Max-Flow Algorithms for Energy Minimization in Vision.” IEEE Transactions on Pattern Analysis and Machine Intelligence, 26(9), 1124-1137.
Korte, B., Vygen, J. (2018). Combinatorial Optimization: Theory and Algorithms. 6th edition, Springer.
Ahuja, R. K., Magnanti, T. L., Orlin, J. B. (1993). Network Flows: Theory, Algorithms, and Applications. Prentice Hall.

上一篇: Tarjan 算法族

下一篇: 拓扑排序

相关阅读: - 最小生成树 - 图着色与寄存器分配

目录

一、最大流问题的形式化定义

流网络

可行流

流值

线性规划视角

二、Ford-Fulkerson 方法与增广路径

残量网络

增广路径

算法框架

终止性与复杂度

一个经典陷阱

三、Edmonds-Karp 算法：BFS 增广

核心改进

时间复杂度

伪代码

实践表现

四、Dinic 算法：分层图与阻塞流

分层图的构造

阻塞流

算法流程

阻塞流的求解：DFS + 当前弧优化

时间复杂度分析

单位容量图上的特殊复杂度

五、最大流最小割定理

割的定义

定理陈述

弱对偶性（容易的方向）

强对偶性（通过 Ford-Fulkerson 终止条件）

LP 对偶视角

最小割的求解

六、二分匹配与最大流归约

二分图匹配问题

通过最大流求解

Hall 定理

Konig 定理

七、匈牙利算法与加权匹配

匈牙利算法（Kuhn-Munkres）

算法思想

算法流程

时间复杂度

与最小费用流的关系

八、Hopcroft-Karp 算法

动机

算法框架

时间复杂度

与 Dinic 的关系

九、最小费用最大流

问题定义

连续最短路算法（SSP）

处理负权边

SPFA 加速

Primal-Dual 方法

应用场景

十、Dinic 算法的完整 C 实现

实现要点

十一、实际应用与工程经验

航线调度

图像分割

棒球淘汰赛判定

工程实践中的注意事项

算法选型指南

十二、个人思考与总结

网络流理论的美

学习路径建议

竞赛中的经验

工程中的考量

最后的话

参考文献