最大流：补给线的极限运力

最大流：补给线的极限运力

冷战年月里，两位美国数学家接到的课题带着硝烟味：苏联的铁路网摆在那里，若想把物资从内陆源源运往西线，整张网的极限运力是多少？要切断它，最少得炸掉哪几段？Ford 与 Fulkerson 为这道题发明的框架，后来成为组合优化史上被引用最多的成果之一。远征队的补给线之战在本章打响，本节建立"流"的模型，推演残余网络与增广路这对核心机制，实现 Edmonds-Karp 算法——它是第 3 章广度优先在容量世界里的第二次登场。

战役背景：流的模型

网络流的标准形：一张有向图，指定一个源（物资只出不进）与一个汇（只进不出），每条边带容量（单位时间可通行的上限）。一个流给每条边分配一个流量，满足两条铁律——容量约束（流量不超容量）与流量守恒（除源汇外，每个顶点进多少出多少）。目标：让从源流入汇的净流量（流值）最大。

模型的力量在于翻译面极广。运力问？吨每小时。通信问？带宽。资金问？额度。任务分派问？任务量。凡"有限通道、要送东西"的场景几乎都能套进来；不少看似无关的问题（图像分割、棒球淘汰判定、项目选址）稍加变形后也归它管——本节末尾给一个 surprising 的例子。

思路推演：残余网络与增广路

从零流起步，怎么把流值一路推高？直觉的做法是找一条从源到汇、还有富余容量的路径，往上灌。但直接灌会犯短视的错误：某条路径提前占死了别的路径需要的边。发明家的妙手是残余网络：在当前流之上重新画一张"还能怎么调整"的图——每条边上的富余量叫残余容量（原容量减当前流量），同时给每条已经过流的边配一条反向边，容量恰等于当前流量，含义是"这些流量可以反悔退回"。

在残余网络里找一条源到汇的通路（增广路），把整条路上的流量抬高（抬的量是路上最小残余容量，即瓶颈），当前流值就上涨。涨完后重画残余网络，再找下一条增广路，直到残余网络里源汇不通——此时当前流是否就是最大流？是的，但证明要到下一节借"最小割"这枚图章才能盖完。反向边是整个机制的灵魂：它给了算法"反悔"的权力，前面贪心占错的通道可以在后续增广里被部分退回重排。没有反向边，贪心选错一步就永远错下去。

算法步骤与实现

Edmonds-Karp 在 Ford-Fulkerson 框架上只改一处：用广度优先找增广路（即每次选跳数最少的增广路）。这一处修改换来两个保证：算法必然终止、总代价与"顶点数乘边数再乘最大流值"同阶。完整实现：

from collections import deque
import networkx as nx

def edmonds_karp(G, s, t):
    """Edmonds-Karp 最大流：返回 (最大流值, 每条边的流量)"""
    R = nx.algorithms.flow.build_residual_network(G, "capacity")
    flow = 0
    while True:
        # 广度优先在残余网络中找 s→t
        parent = {s: None}
        q = deque([s])
        while q and t not in parent:
            u = q.popleft()
            for v, attr in R[u].items():
                if v not in parent and attr["capacity"] - attr["flow"] > 1e-9:
                    parent[v] = u
                    q.append(v)
        if t not in parent:                 # 残余网络已断流
            break
        # 求瓶颈
        path, v = [], t
        while parent[v] is not None:
            path.append((parent[v], v))
            v = parent[v]
        bottleneck = min(R[u][v]["capacity"] - R[u][v]["flow"] for u, v in path)
        for u, v in path:                   # 正向加流，反向登记反悔权
            R[u][v]["flow"] += bottleneck
            R[v][u]["flow"] -= bottleneck
        flow += bottleneck
    return flow, R

supply = nx.DiGraph()
supply.add_edge("基地", "中转A", capacity=3)
supply.add_edge("基地", "中转B", capacity=2)
supply.add_edge("中转A", "前哨", capacity=2)
supply.add_edge("中转B", "前哨", capacity=3)
supply.add_edge("中转A", "中转B", capacity=2)
value, R = edmonds_karp(supply, "基地", "前哨")
print("最大流值:", value)
print("nx 对照:", nx.maximum_flow_value(supply, "基地", "前哨"))
​

代码里借 networkx 的残余网络构造器统一了容量登记（含反向边初始化为负流量、容量为零的技巧——负流量表示"反向可用量"），自己实现增广主循环。与官方结果对照一致后再看每条边的实流：

def report_flow(G, R):
    """从残余网络读出每条原边的实流"""
    for u, v, d in G.edges(data=True):
        print(f"{u} → {v}: {R[u][v]['flow']}/{d['capacity']}")

report_flow(supply, R)
​

读数时留意流量守恒：中转站进出相等，源出净量恰等于汇入净量、等于流值——这是检验实现正确性的第一现场。

复杂度与正确性

Edmonds-Karp 的代价账单是"顶点数乘边数的平方"量级。证明的骨架很妙：每次沿最短增广路推流后，源到任何顶点的最短距离单调不减（反向边的更新只会让距离阶梯变平）；而每条边成为"瓶颈"的次数被顶点数限制，总增广轮数被"顶点数乘边数"封顶。对照原始的 Ford-Fulkerson（任意选路）：若容量是无理数，构造出的输入能让它永远不终止；即使全是整数，也可能为了一点流值绕远路成千上万轮。广度优先的最短选路并非"更快找到路"这么肤浅，它系统性地杜绝了反复横跳的病态模式——又一次印证第 3 章的老话：队列的层次性自带秩序。

正确性的另一半（"残余断流即最大"）属于下一节的最大流最小割定理，此处先把直觉压成一句：残余网络断流时，从源可达的顶点集与它的补集之间横着一组被榨干的边，它们构成一柄恰好等于当前流值的"闸门"——闸门挡着，流就不可能更大；闸门又恰好被灌满，当前流已然顶到闸门。

应用与变体

建模能力是本节真正的珍宝。棒球淘汰判定是教科书级 surprising 案例：一支球队是否已数学上无缘夺冠，可以转写成"其余球队之间的对局能否合理分配胜负使某队无法反超"的流问题，最大流跑不满即淘汰。图像分割把像素设为顶点、相邻相似度设为边权，源汇分别代表前景与背景，最小割（下节主角）切开的正是物体轮廓。变体方面：多源多汇添一个超级源与超级汇即可；点容量把顶点拆成"入点出点"夹一条容量边；费用流给每条边再加单位费用，在最大流里挑最便宜的一类（残余网络加最短路引擎，正是第 5 章 Bellman-Ford 的负权本领派上用场的地方）。

⚠️ 常见坑：用浮点容量又用严格相等判断"满流"。容量运算的浮点误差会让"余量为零"的判断随机失灵；工程做法是用整数容量，或给比较留一个容差。

💡 关键直觉：把残余网络想成谈判桌——正向边是"还能让多少"，反向边是"可以退回多少"。最大流算法不是一次性拍板，而是多轮讨价还价直到再无交易可做。

运力求出来了。可断流的那道"闸门"到底在哪几条边上？下一节把敌方的视角翻开——最小割，与最大流互为镜像的另一半。