经典算法专栏 #09：网络流与匹配

网络流的核心问题是：如何把有限资源从源点最大化地运送到汇点？ 最大流-最小割定理揭示了一个深刻对偶：系统的最大吞吐量恰好等于最薄弱截面的容量。本文不止给代码——重点讲清反向边为什么能"反悔"、增广路怎么一步步推进、二分图匹配与最大流的等价性。对应《算法导论》第 26 章。

目录

流网络与残差网络

基本定义

流网络 G = (V, E, c, s, t)：

• 容量函数 c(u,v)：边 (u,v) 的最大流量，c(u,v)=0 表示边不存在
• 流函数 f(u,v)：实际流量，满足：
  • 容量约束：0 ≤ f(u,v) ≤ c(u,v)
  • 流量守恒：对所有 v≠s,t，流入量 = 流出量
• 最大流值：|f| = 从 s 流出的总量

反向边的本质：允许"反悔"

残差网络 G_f 中每条边 (u,v) 对应两条残差边：

正向残差边 (u→v)：残差容量 = c(u,v) - f(u,v)，表示"还能再增加多少流量"
反向残差边 (v→u)：残差容量 = f(u,v)，表示"可以取消多少已有流量"

为什么反向边是正确的：

考虑这个图：
s →(10)→ A →(10)→ t
s →(10)→ B →(10)→ t
A →(1)→  B

如果第一轮贪心找到路径 s→A→B→t（流 1），
此时 A→t 还有 9，B 的入边只剩 9，
若第二轮沿 s→B→t 流 9，再沿 s→A→t 流 9，实际最大流 = 10+10 = 20。

但贪心已经"错误地"从 A→B 流了 1，
通过残差网络的反向边 B→A，可以"撤销"这 1 单位流，
相当于重新规划路由，达到最优解。

Ford-Fulkerson：增广路完整演示

手推增广过程

网络如下（每条边格式为"容量"）：

flowchart LR
    s -->|"16"| A
    s -->|"13"| B
    A -->|"12"| B
    A -->|"10"| C
    B -->|"14"| D
    B -->|"4"| C
    C -->|"9"| t
    D -->|"7"| C
    D -->|"20"| t

    style s fill:#dae8fc,stroke:#6c8ebf
    style t fill:#f8cecc,stroke:#b85450

初始状态：所有边流量 = 0，残差容量 = 原容量。

第 1 轮：找增广路 s→A→C→t，瓶颈 = min(16,10,9) = 9

更新：s→A: 16-9=7剩余, A→C: 10-9=1剩余, C→t: 9-9=0剩余
反向边：A→s 增加 9，C→A 增加 9，t→C 增加 9
最大流 += 9

第 2 轮：C→t 已满，找 s→B→D→t，瓶颈 = min(13,14,20) = 13

更新：s→B: 0剩余, B→D: 14-13=1剩余, D→t: 20-13=7剩余
最大流 += 13，累计 22

第 3 轮：找 s→A→B→C→... C→t 已满，换路 s→A→B→D→t，瓶颈 = min(7,12,1,7) = 1

更新各边，最大流 += 1，累计 23

第 4 轮：无增广路，最大流 = 23。

int fordFulkerson(int[][] cap, int s, int t, int n) {
    int maxFlow = 0;
    int[][] res = new int[n][n];
    for (int i = 0; i < n; i++)
        System.arraycopy(cap[i], 0, res[i], 0, n);

    int[] path = new int[n];
    while (dfs(res, s, t, n, path)) {
        // 找路径瓶颈
        int flow = Integer.MAX_VALUE;
        for (int v = t; v != s; v = path[v])
            flow = Math.min(flow, res[path[v]][v]);
        // 更新残差网络
        for (int v = t; v != s; v = path[v]) {
            res[path[v]][v] -= flow;
            res[v][path[v]] += flow;
        }
        maxFlow += flow;
    }
    return maxFlow;
}

boolean dfs(int[][] res, int s, int t, int n, int[] path) {
    boolean[] visited = new boolean[n];
    visited[s] = true;
    Deque<Integer> stack = new ArrayDeque<>();
    stack.push(s);
    while (!stack.isEmpty()) {
        int u = stack.pop();
        for (int v = 0; v < n; v++) {
            if (!visited[v] && res[u][v] > 0) {
                visited[v] = true;
                path[v] = u;
                if (v == t) return true;
                stack.push(v);
            }
        }
    }
    return false;
}
// O(E·|f*|)：每次增广至少增加 1 单位，|f*| 为最大流值
// 容量为有理数时可能不终止 → 用 Edmonds-Karp

Edmonds-Karp：保证多项式终止

改进：用 BFS 找最短增广路（边数最少），而不是任意路径。

为什么 BFS 能保证多项式终止：

定理：每次增广后，每条边的"瓶颈"被使用后，
     在下次成为瓶颈之前，s 到它的距离至少增加 2。
     每条边最多成为 O(V) 次瓶颈。
     共 O(E) 条边 → 总增广次数 ≤ O(VE)
     每次 BFS O(E) → 总时间 O(VE²)

int edmondsKarp(int[][] cap, int s, int t, int n) {
    int maxFlow = 0;
    int[][] res = new int[n][n];
    for (int i = 0; i < n; i++) System.arraycopy(cap[i], 0, res[i], 0, n);

    int[] parent = new int[n];
    while (bfs(res, s, t, n, parent)) {
        int flow = Integer.MAX_VALUE;
        for (int v = t; v != s; v = parent[v])
            flow = Math.min(flow, res[parent[v]][v]);
        for (int v = t; v != s; v = parent[v]) {
            res[parent[v]][v] -= flow;
            res[v][parent[v]] += flow;
        }
        maxFlow += flow;
    }
    return maxFlow;
}

boolean bfs(int[][] res, int s, int t, int n, int[] parent) {
    boolean[] visited = new boolean[n];
    visited[s] = true;
    Arrays.fill(parent, -1);
    Queue<Integer> queue = new LinkedList<>();
    queue.offer(s);
    while (!queue.isEmpty()) {
        int u = queue.poll();
        for (int v = 0; v < n; v++) {
            if (!visited[v] && res[u][v] > 0) {
                visited[v] = true;
                parent[v] = u;
                if (v == t) return true;
                queue.offer(v);
            }
        }
    }
    return false;
}

Dinic：分层图加速

核心思想

Edmonds-Karp 每轮只找一条增广路，Dinic 每轮找所有不能再短的增广路（阻塞流），大幅减少 BFS 轮次。

两步走：

① BFS 按 s 的距离给节点分层（构造层次图）
② 在层次图上 DFS 找阻塞流（一次找到所有沿层前进的增广路）
③ 重复，直到 t 在层次图中不可达

为什么 O(V²E)：

层次图中 s 到 t 的距离单调递增（每轮至少 +1）
→ 最多 O(V) 轮 BFS
每轮 DFS 找阻塞流：O(VE)（每次 DFS 从失败节点剪枝）
总时间：O(V) × O(VE) = O(V²E)

特例：单位容量图（二分图匹配）中阻塞流 O(E)，
总时间 O(V^0.5 · E)，比 O(VE) 快很多

// 生产级 Dinic（邻接表实现，支持大图）
class Dinic {
    int n;
    int[] head, nxt, to, cap, level, iter;
    int cnt = 0;

    Dinic(int n) {
        this.n = n;
        head = new int[n]; Arrays.fill(head, -1);
        // 预分配足够空间
        nxt = new int[200010]; to = new int[200010];
        cap = new int[200010];
        level = new int[n]; iter = new int[n];
    }

    void addEdge(int u, int v, int c) {
        // 成对添加正向边和反向边（cnt 偶数为正向，cnt^1 为反向）
        to[cnt] = v; cap[cnt] = c; nxt[cnt] = head[u]; head[u] = cnt++;
        to[cnt] = u; cap[cnt] = 0; nxt[cnt] = head[v]; head[v] = cnt++;
    }

    boolean bfs(int s, int t) {
        Arrays.fill(level, -1);
        level[s] = 0;
        Queue<Integer> q = new LinkedList<>();
        q.offer(s);
        while (!q.isEmpty()) {
            int u = q.poll();
            for (int e = head[u]; e != -1; e = nxt[e]) {
                if (cap[e] > 0 && level[to[e]] < 0) {
                    level[to[e]] = level[u] + 1;
                    q.offer(to[e]);
                }
            }
        }
        return level[t] >= 0;
    }

    int dfs(int u, int t, int pushed) {
        if (u == t) return pushed;
        for (; iter[u] != -1; iter[u] = nxt[iter[u]]) {
            int e = iter[u], v = to[e];
            if (cap[e] > 0 && level[v] == level[u] + 1) {
                int d = dfs(v, t, Math.min(pushed, cap[e]));
                if (d > 0) {
                    cap[e] -= d; cap[e ^ 1] += d;  // e^1 是对应的反向边
                    return d;
                }
            }
        }
        return 0;
    }

    int maxflow(int s, int t) {
        int flow = 0, f;
        while (bfs(s, t)) {
            System.arraycopy(head, 0, iter, 0, n);
            while ((f = dfs(s, t, Integer.MAX_VALUE)) > 0)
                flow += f;
        }
        return flow;
    }
}

最大流-最小割定理

s-t 割的定义

s-t 割（S, T）：将 V 划分为含 s 的集合 S 和含 t 的集合 T，割的容量为从 S 到 T 方向的所有边的容量之和：

c(S,T) = Σ c(u,v)，其中 u∈S, v∈T

关键不等式：对任意流 f 和任意割 (S,T)：

|f| ≤ c(S,T)

证明：
|f| = 流过割的净流量
    = Σ f(u,v) - Σ f(v,u)   (u∈S, v∈T)
    ≤ Σ f(u,v)               (流量非负)
    ≤ Σ c(u,v) = c(S,T)     (容量约束)

即：任意流的值 ≤ 任意割的容量

定理与完整证明

最大流-最小割定理：|f*| = min{c(S,T)}，最大流 = 最小割。

证明（三个等价命题互推）：

(1)→(2)：f 是最大流 → 残差网络无增广路

反证：若存在增广路 p，沿 p 增加流量，得到更大的流，矛盾。

(2)→(3)：残差网络无增广路 → 存在割容量 = 流量

设 S = 残差网络中从 s 可达的节点集合，T = V - S
由于无增广路，t ∉ S

对每条跨越割 (u∈S, v∈T) 的原图边 (u,v)：
  若 f(u,v) < c(u,v)，则残差边 u→v 存在，v 可达，v 应在 S → 矛盾
  因此 f(u,v) = c(u,v)（所有从 S 到 T 的边都满载）

对每条跨越割 (v∈T, u∈S) 的原图边 (v,u)：
  若 f(v,u) > 0，则残差边 u→v 存在，v 可达，v 应在 S → 矛盾
  因此 f(v,u) = 0（所有从 T 到 S 的边都为空）

|f| = Σf(u,v) - Σf(v,u) = Σc(u,v) - 0 = c(S,T)
即存在割其容量等于流量 ✅

(3)→(1)：割容量 = 流量 → f 是最大流

由不等式 |f| ≤ c(S,T)，若等号成立，则 f 已达任意割的下界，
不可能有更大的流 → f 是最大流 ✅

直觉：最薄弱的截面

最小割就是网络的瓶颈截面——无论怎么安排路由，流量都受限于这个截面的总容量。最大流算法找到的流量值，恰好等于这个瓶颈的容量。

二分图匹配

增广路定义与例题

交替路径：从未匹配点出发，沿"非匹配边→匹配边→非匹配边→..."交替前进。 增广路：交替路径的终点也是未匹配点。沿增广路翻转匹配状态，匹配数 +1。

完整例题：4 名工人（1~4）和 4 个任务（A~D），能力矩阵如下：

工人1: 可做 A, B
工人2: 可做 B, C
工人3: 可做 C, D
工人4: 可做 A, D

graph LR
    W1["工人1"] --- A
    W1 --- B
    W2["工人2"] --- B
    W2 --- C
    W3["工人3"] --- C
    W3 --- D
    W4["工人4"] --- A
    W4 --- D

匈牙利算法执行过程（初始匹配为空）：

工人1 尝试任务A → A 未匹配 → 匹配(1,A)，匹配数=1

工人2 尝试任务B → B 未匹配 → 匹配(2,B)，匹配数=2

工人3 尝试任务C → C 未匹配 → 匹配(3,C)，匹配数=3

工人4 尝试任务A → A 已被工人1 占用
  工人1 能否换到其他任务？
    工人1 尝试任务B → B 已被工人2 占用
      工人2 能否换到其他任务？
        工人2 尝试任务C → C 已被工人3 占用
          工人3 能否换到其他任务？
            工人3 尝试任务D → D 未匹配！
            匹配(3,D)，工人3 从 C 移到 D
          工人2 获得 C，匹配(2,C)，工人2 从 B 移到 C
        工人1 获得 B，匹配(1,B)，工人1 从 A 移到 B
      工人4 获得 A，匹配(4,A)

最终匹配：{(1,B), (2,C), (3,D), (4,A)}，匹配数=4（完美匹配！）

这就是一条增广路：4→A→1→B→2→C→3→D（长度 7，翻转后 3 对匹配各自移动）

boolean dfs(int u, boolean[] vis, int[] match, List<List<Integer>> adj) {
    for (int v : adj.get(u)) {
        if (!vis[v]) {
            vis[v] = true;
            if (match[v] == -1 || dfs(match[v], vis, match, adj)) {
                match[v] = u;
                return true;  // 找到增广路，翻转匹配
            }
        }
    }
    return false;
}

int hungarian(List<List<Integer>> adj, int uSize, int vSize) {
    int[] match = new int[vSize];
    Arrays.fill(match, -1);
    int res = 0;
    for (int u = 0; u < uSize; u++) {
        boolean[] vis = new boolean[vSize];
        if (dfs(u, vis, match, adj)) res++;
    }
    return res;
}
// 时间 O(VE)：每次 DFS O(E)，共 V 次

König 定理：匹配与覆盖的对偶

定理：二分图中，最大匹配数 = 最小顶点覆盖数。

最小顶点覆盖：最少的顶点集合 C，使得每条边至少有一个端点在 C 中。

直觉：匹配的每条边都需要至少一个端点覆盖它，因此 |覆盖| ≥ |匹配|。König 定理说二者相等，等号可达。

通过最大流求最小顶点覆盖：

1. 跑匈牙利/最大流求最大匹配
2. 从所有未匹配的左侧节点出发，BFS/DFS 沿"非匹配边→匹配边"交替遍历
3. 最小覆盖 = 左侧被访问的节点 ∪ 右侧未被访问的节点

与最大流的等价

建图：超级源 s 连接所有左侧节点（容量 1），所有右侧节点连接超级汇 t（容量 1），二分图边（容量 1），跑最大流：

最大流值 = 最大匹配数

证明：
每条流量为 1 的 s→u→v→t 路径，对应一条匹配边 (u,v)
流量守恒保证每个节点至多匹配一次
→ 最大流 ↔ 最大匹配一一对应

建图模板与实际应用

邻接表建图（Dinic 实战模板）

// 典型建图方式（cnt 从 0 开始，正向边偶数，反向边奇数）
Dinic dinic = new Dinic(n + 2);  // n个节点 + 超级源 + 超级汇
int s = n, t = n + 1;

// 添加一条正向边（反向边容量自动为0）
dinic.addEdge(u, v, capacity);

// 最大流
int ans = dinic.maxflow(s, t);

典型题型建模

点容量拆点建图

当节点有容量限制时（每个节点只能流过有限量），拆点：

原节点 v 拆成 v_in 和 v_out：
  v_in → v_out 容量 = 节点容量
  所有进入 v 的边 → 进入 v_in
  所有从 v 出发的边 → 从 v_out 出发

参考资料

• 《算法导论》（CLRS）第 3 版 — 第 26 章网络流
• 《算法竞赛进阶指南》— 网络流与二分图章节
• 《图论及其应用》— 最大流-最小割定理的历史背景（Ford & Fulkerson，1956）
• 图算法（BFS 是 Edmonds-Karp 和 Dinic 分层的基础；DFS 是 Ford-Fulkerson 增广的基础）
• 算法复杂度分析（Dinic O(V²E) 和二分图特例 O(E√V) 的推导）