最大流最小割

一、直观理解：管道系统里最多能输送多少，瓶颈在哪

在容量网络中，每条弧有容量 $c(u,v)$。从源 $s$ 到汇 $t$ 的流要满足：

1. 容量约束：$0\le f(u,v)\le c(u,v)$；
2. 守恒：中间点流入=流出。

最大流是 $s$ 净流出（或 $t$ 净流入）的最大值。

割 $(S,T)$ 把点分成含 $s$ 的 $S$ 与含 $t$ 的 $T$，割的容量是从 $S$ 指向 $T$ 的边容量之和。瓶颈直觉：任何流都不能超过任何割；而最大流恰好等于最小割容量——这就是最大流最小割定理。

因此，算出最大流的同时，也找到了“卡脖子”的边集合，解释性极强。

二、适用场景与优缺点

类型	说明
适用场景	运输/通信上限；二部图匹配可归约到流；图像分割（图割）；应急疏散上限；供应链瓶颈分析。
核心优点	有强对偶（min-cut）证书；算法多样；建模可扩展到多源多汇（连超级源汇）。
局限与缺点	经典模型无费用（费用见最小费用流）；边无增益；动态时变容量需扩展；实现要注意残量网络细节。

三、核心原理

1. 残量网络

对弧 $(u,v)$，残量 $c_f(u,v)=c(u,v)-f(u,v)$，并允许反向残量 $f(u,v)$ 用于“撤销”。

2. 增广路（Ford–Fulkerson 思想）

在残量网中找 $s\to t$ 路径，沿路增广，直到不存在增广路。此时 $S=$ 残量网中 $s$ 可达集合，$(S,V\setminus S)$ 即最小割。

3. 算法

• Edmonds–Karp：BFS 找最短增广路，$O(nm^2)$；
• Dinic：分层网 + 多路增广，更高效；
• 预流推进等。

4. 整数定理

容量整数则存在整数最大流——匹配等问题常用。

四、关键决策

1. 多源多汇

超级源连所有源，所有汇连超级汇，容量按供应/需求。

2. 顶点容量

拆点 $v_{in}\to v_{out}$，边容量为点容。

3. 无向边

建模为双向弧，容量同，或按题意处理。

4. 验证

流守恒、不超容量、最大流值=最小割容量。

五、MATLAB 示例

% s=1, t=6
s = [1 1 2 2 3 3 4 5];
t = [2 3 3 4 4 5 6 6];
c = [10 10 4 8 9 4 10 10];
G = digraph(s, t, c);
[mf, GF, cs, ct] = maxflow(G, 1, 6);
fprintf("最大流 = %g\n", mf);
disp("最小割 s 侧节点:"); disp(cs');
disp("最小割 t 侧节点:"); disp(ct');

figure;
p = plot(G, "EdgeLabel", G.Edges.Weight);
% 高亮割边：从 cs 到 ct
highlight(p, cs, "NodeColor", "r");
title(sprintf("最大流=%g", mf));

% ---- 手写 Edmonds-Karp ----
n = 6;
C = zeros(n);
for e = 1:numel(s)
    C(s(e), t(e)) = c(e);
end
F = zeros(n);
function [parent, found] = bfs_aug(C, F, s0, t0)
    n = size(C,1);
    parent = -ones(1,n);
    vis = false(1,n);
    q = s0; vis(s0)=true; parent(s0)=0;
    head = 1;
    while head <= numel(q)
        u = q(head); head = head+1;
        for v = 1:n
            if ~vis(v) && C(u,v)-F(u,v) > 1e-12
                vis(v)=true; parent(v)=u; q(end+1)=v; %#ok<AGROW>
                if v==t0, found=true; return; end
            end
        end
    end
    found = false;
end

while true
    [parent, found] = bfs_aug(C, F, 1, 6);
    if ~found, break; end
    % 找瓶颈
    add = inf; v = 6;
    while v ~= 1
        u = parent(v);
        add = min(add, C(u,v)-F(u,v));
        v = u;
    end
    v = 6;
    while v ~= 1
        u = parent(v);
        F(u,v) = F(u,v) + add;
        F(v,u) = F(v,u) - add;
        v = u;
    end
end
maxflow_hand = sum(F(1,:));
fprintf("手写 EK 最大流=%g\n", maxflow_hand);
disp("流量矩阵 F:"); disp(F);

六、如何解释结果

1. 网络含义、容量单位；
2. 最大流值与可行流（可列表关键弧流量）；
3. 最小割分区与跨割边——瓶颈解释；
4. 改进建议：扩容割边可提高总流；
5. 算法与验证（流=割）。

七、常见误区

1. 把最短路当最大流

目标完全不同。

2. 忘记反向边

残量实现错误会导致流偏小。

3. 割的容量算成割内边

只算 $S\to T$ 方向。

4. 点有容量却不拆点

模型错。

八、小结

最大流最小割的核心是：

增广至无增广路时，流值等于 $s$ 可达集给出的最小割容量。

它既给数量（能运多少），也给结构解释（瓶颈在哪）。建模时正确处理多源汇、点容与残量网络，并用 min-cut 做结果证书。