网络流

00:00

3 min Advanced 2026/6/14

网络流算法：最大流 Ford-Fulkerson 方法、Edmonds-Karp 算法、残量图与增广路径。

1. 网络流基础

1.1 流网络定义

有向图 $G = (V, E)$
源点 $s$ ，汇点 $t$
容量 $c (u, v) \geq 0$
流量 $f (u, v)$ 满足：
- 容量约束： $0 \leq f (u, v) \leq c (u, v)$
- 流量守恒： $\sum_{u} f (u, v) = \sum_{w} f (v, w)$ （中间节点）

1.2 最大流问题

求从 $s$ 到 $t$ 的最大流量：

$∣ f ∣ = \sum_{v} f (s, v) - \sum_{u} f (u, s)$

2. Ford-Fulkerson 方法

2.1 核心思想

反复寻找增广路径，增加流量直到无法增广：

1. 初始化流为0
2. 在残量图中寻找 s→t 的增广路径
3. 沿路径增加流量（增加量为路径最小残量）
4. 更新残量图
5. 重复直到无增广路径

2.2 残量图

$c_{f} (u, v) = c (u, v) - f (u, v)$

反向边容量为当前流量，允许”撤销”：

$c_{f} (v, u) = f (u, v)$

2.3 实现

from collections import deque

def edmonds_karp(capacity, s, t):
    n = len(capacity)
    flow = [[0] * n for _ in range(n)]
    max_flow = 0

    while True:
        # BFS 寻找增广路径
        parent = [-1] * n
        parent[s] = s
        queue = deque([s])

        while queue and parent[t] == -1:
            u = queue.popleft()
            for v in range(n):
                if parent[v] == -1 and capacity[u][v] - flow[u][v] > 0:
                    parent[v] = u
                    queue.append(v)

        if parent[t] == -1:
            break  # 无增广路径

        # 计算增广量
        aug = float('inf')
        v = t
        while v != s:
            u = parent[v]
            aug = min(aug, capacity[u][v] - flow[u][v])
            v = u

        # 更新流量
        v = t
        while v != s:
            u = parent[v]
            flow[u][v] += aug
            flow[v][u] -= aug
            v = u

        max_flow += aug

    return max_flow

3. Edmonds-Karp 算法

3.1 与 Ford-Fulkerson 的区别

Edmonds-Karp 使用 BFS 寻找最短增广路径，保证多项式时间：

Ford-Fulkerson: 增广路径选择任意 → 可能不收敛（容量为无理数时）
Edmonds-Karp:   BFS 最短路径 → O(VE^2)

3.2 复杂度分析

每次 BFS: O(E)
增广次数: O(VE)
总时间: O(VE^2)

关键证明: 最短增广路径长度单调不减
每条边最多成为关键边 O(V) 次

4. 最大流最小割定理

4.1 割的定义

割 $(S, T)$ 将顶点分为两部分， $s \in S$ , $t \in T$ ：

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

4.3 求最小割

def min_cut(capacity, flow, s):
    n = len(capacity)
    visited = [False] * n
    queue = deque([s])
    visited[s] = True

    while queue:
        u = queue.popleft()
        for v in range(n):
            if not visited[v] and capacity[u][v] - flow[u][v] > 0:
                visited[v] = True
                queue.append(v)

    # S = visited 的顶点, T = 未访问的顶点
    cut_edges = []
    for u in range(n):
        for v in range(n):
            if visited[u] and not visited[v] and capacity[u][v] > 0:
                cut_edges.append((u, v))
    return cut_edges

5. 应用

5.1 二分图最大匹配

def bipartite_matching(left_size, right_size, edges):
    n = left_size + right_size + 2
    s, t = 0, n - 1
    capacity = [[0] * n for _ in range(n)]

    # 源到左部
    for i in range(1, left_size + 1):
        capacity[s][i] = 1

    # 右部到汇
    for j in range(left_size + 1, n - 1):
        capacity[j][t] = 1

    # 左到右的边
    for u, v in edges:
        capacity[u + 1][v + left_size + 1] = 1

    return edmonds_karp(capacity, s, t)

| 算法 | 时间复杂度 | 特点 | | -------------- | ---------- | ---------- | --- | ---------- | | Ford-Fulkerson | $O (E \cdot ∣ f^{\*} ∣)$ | 可能不收敛 | | Edmonds-Karp | $O (V E^{2})$ | BFS 最短路 | | Dinic | $O (V^{2} E)$ | 分层图 | | Push-Relabel | $O (V^{3})$ | 高效实现 | | ISAP | $O (V^{2} E)$ | 简化 Dinic |

网络流