5.2 最大流与最小割

5.2 最大流与最小割

本节摘要：最大流问题问"网络从源到汇最多能压过多少流量"，最小割问"掐断哪组边代价最小地切断连通"。最大流最小割定理宣告两者相等，是组合优化里对偶思想的代表。本节手写增广路径算法，演示残量网络与反向边的机理，并给出从物流管网到图片分割的应用光谱。

水务公司的两难

水务公司从水库向城区供水，管网由泵站与管道组成，每段管道有容量上限。规划科的两个问题看似无关：一是全网每天最多能供多少水（最大流）；二是如果要做检修，最少关掉哪几段管道就能让城区彻底断水（最小割）。1956 年福特与富尔克森证明：这两个数相等。最大流是多少，最便宜的"掐断方案"就值多少——网络能压过的极限流量，恰好卡在最窄的那束瓶颈管段上。

增广路径：贪心加一次反悔机制

求最大流的主流框架是增广路径法：反复找一条从源到汇、还有剩余容量的路径，往上面压流量，直到找不出这样的路径。单纯贪心有个陷阱：先压错的流量可能堵死更优的布局。解法优雅得惊人——每条边配一条容量同步更新的反向边，相当于给算法一次反悔的通道：后续增广可以把先前压上去的流量"退回来"改道。这个残量网络（残余容量构成的图）是整个算法的灵魂：

from collections import deque

def max_flow(cap, s, t):
    """cap: 节点数固定的容量矩阵；返回总流量与残量网络"""
    n = len(cap)
    residual = [row[:] for row in cap]
    flow = 0
    while True:
        # BFS 找残量网络中 s 到 t 的最短增广路径（Edmonds-Karp）
        parent = [-1] * n
        parent[s] = s
        q = deque([s])
        while q and parent[t] == -1:
            u = q.popleft()
            for v in range(n):
                if parent[v] == -1 and residual[u][v] > 0:
                    parent[v] = u
                    q.append(v)
        if parent[t] == -1:
            return flow, residual
        # 沿路径找瓶颈容量
        bottleneck = float("inf")
        v = t
        while v != s:
            bottleneck = min(bottleneck, residual[parent[v]][v])
            v = parent[v]
        # 正向减、反向加（反悔通道）
        v = t
        while v != s:
            u = parent[v]
            residual[u][v] -= bottleneck
            residual[v][u] += bottleneck
            v = parent[v]
        flow += bottleneck

cap = [[0, 9, 9, 0, 0, 0],
       [0, 0, 4, 8, 0, 0],
       [0, 0, 0, 0, 10, 0],
       [0, 0, 0, 0, 6, 0],
       [0, 0, 0, 0, 0, 10],
       [0, 0, 0, 0, 0, 0]]
flow, residual = max_flow(cap, 0, 5)
print("最大流 =", flow)      # 17
​

用 BFS 挑增广路径的版本叫 Edmonds-Karp，多一项"边数最少"的规矩，换来多项式时间的保证（O(VE²)）。算法终止时，从源点在残量网络里还能到达的节点集合 S，与到达不了的集合 T，构成一个割——S 指向 T 的那些边全部满载，它们就是最小割，也正是瓶颈管段。给水务公司的检修答案，就藏在这最后一步的残量网络里。

增广与反悔的现场

为什么说它是"对偶"

第 3 章线性规划里，原问题与对偶问题一个求最优方案、一个给资源定价。最大流最小割是同一出戏的图上版本：最大流是"怎么做"（原问题），最小割是"瓶颈在哪、值多少钱"（对偶/证书）。算法终止时给出的那个割，就是流值的最优性证明——你不必相信算法跑对了，只需检查那几条满载边，容量之和等于流量，最优性即被第三方验证。这种"解 + 证书"的结构在整数规划里对应分支定界的间隙，在近似算法里对应近似比，是组合优化反复出现的母题。

应用光谱

最大流的结构出现在远比水管更宽的场合。二分图匹配：任务与人之间的可行分配，加一个源一个汇即化归为最大流（婚配模型是它的通俗版）。项目选址与图像分割：图像里像素与"前景/背景"两个标签的亲和度构成网络，最小割恰好是把图劈成两半的最平滑边界——GrabCut 类算法的数学内核。疏散与交通容量：场馆疏散能力评估、路网高峰承载测算，本质都是带容量约束的流。第 9 章的物流战例会把最大流与最短路拼进同一个决策流水线。

💡 关键直觉：见到"容量 + 分配"四个字，先想流网络。很多看似定制的问题，加一对虚拟源汇就现出最大流原形，解法与正确性证书一起白拿。

从流的视角看世界：三个换装现场

最大流结构在现实中的换装远超管网。航线安排：空港之间的航班座位是"流量"，各航段容量是机型座位数，一周内能运送的旅客总数就是流值——枢纽机场的容量规划由此变成最大流计算。任务分配：任务配工人，每人有可胜任清单，能同时配对的上限是二分图最大匹配（加虚拟源汇即化归为流），医院排班、课程表冲突消解都用它打底。系统脆弱性：网络中哪组链路被毁会切断通信，答案在最小割里——攻击者眼中的最薄弱环节与设计者眼中的加固优先级，是同一个割的两面。识别换装的要诀是听到"容量、匹配、瓶颈、连通上限"这类词时，心里自动加一对虚拟源汇。流网络的通用性还在于它与第 3 章的血缘：最大流本质是特殊结构的线性规划，单纯形与增广路径是同一座山的两条登山道。

本节要点回顾

• 最大流 = 最小割：能压过的极限流量与最窄瓶颈束相等，解与证书同箱交付；
• 反向边是反悔机制，让贪心增广摆脱先压错后堵死的命运；
• BFS 挑最短增广路径（Edmonds-Karp）换来多项式时间保证；
• 残量网络终态给出最小割：源侧可达集合与汇侧的边界即瓶颈管段；
• 匹配、分割、疏散都是流模型的马甲，识别结构即白拿算法。

路径和流量都是"一个单位从 A 到 B"的问题。下一节把难度拧到头：访问所有点还要回来，顺序本身成为决策——TSP，组合优化的皇冠与试金石。