最大流（Ford-Fulkerson、Dinic）

一、直观理解：在水管网络里从源头向汇点泵最多的水

最大流问题：有向图中每条边有容量 $c(u,v)$，求从源 $s$ 到汇 $t$ 的可行流，使总发送量最大。可行流满足：

1. 容量限制：$0\le f(u,v)\le c(u,v)$（更一般可讨论反对称净流）；
2. 流量守恒：中间点流入=流出。

Ford–Fulkerson 族算法的直观是：不断在残量网络里找一条还能再挤一点流量的增广路，把流量往上推，直到推不动。Dinic 则用分层网络一次推多个阻塞流，通常更快。

最大流最小割定理说：最大流量 = 最小割容量。最小割给出网络的瓶颈边集，解释「卡在哪里」。

二、适用场景与优缺点

类型	说明
适用场景	运输上限、通信带宽、匹配（二分图最大匹配可化最大流）、项目选择与割、排班与流通用建模。
核心优点	多项式算法成熟；最小割可解释瓶颈；可化归众多组合问题；比通用 LP 更贴网络结构。
局限与缺点	经典最大流无费用；多重源汇需连超级源汇；无向边要拆成双向；实现细节（残量、反向边）易错。

使用前确认：

1. 源汇是否唯一，容量是否非负；
2. 是否需要同时最小化费用（若是，见最小费用最大流）；
3. 图规模，选择 FF/EK 还是 Dinic；
4. 是否需要输出每边流量与最小割。

三、核心原理

1. 残量网络

对边 $(u,v)$ 流量 $f$，残量

$$c_f(u,v)=c(u,v)-f(u,v),\quad c_f(v,u)=f(u,v)$$

（反向残量允许「撤销」已推流量。）增广路：残量网络中 $s$ 到 $t$ 的路径。路上可增广的量是路径残量最小值 $\Delta$。

2. Ford–Fulkerson

反复：找任意增广路 → 增广 $\Delta$ → 更新残量，直到无增广路。若容量有理（整数），有限终止；最坏时间依赖容量大小。Edmonds–Karp 用 BFS 找最短（边数）增广路，$O(nm^2)$。

3. Dinic 算法

1. BFS 在残量网络上分层，构造到 $t$ 的层次图；
2. 在层次图上用 DFS 多次增广，得到阻塞流；
3. 重复直到 $t$ 不可达。

单位容量等情形很快，一般 $O(n^2 m)$，实践中对中等图很强。

4. 最大流最小割

$s$-$t$ 割 $(S,T)$：$s\in S,t\in T$，容量 $\sum_{u\in S,v\in T}c(u,v)$。

$$\max\text{ flow}=\min\text{ cut}$$

算法结束时，$S=$ 残量网络中从 $s$ 可达的点集，$(S,V\setminus S)$ 即最小割。

5. 与线性规划

最大流可写 LP，故也可用 linprog，但专用算法通常更快且给出割解释。建模验证时可用 LP 对照小例子。

四、关键决策

1. 实现选型

规模/需求	建议
教学、小图	Edmonds–Karp（BFS FF）
中等图、追求速度	Dinic
只需建模验证	LP / 工具箱

2. 多源多汇

设超级源 $S$ 连所有源（容量为各源供给），所有汇连超级汇 $T$（容量为需求）。

3. 二分图匹配

左连右容量 1，源连左 1，右连汇 1，最大流=最大匹配。

4. 输出方案

除了流量值，报告每条边的 $f(u,v)$ 与最小割边，便于工程改造（扩容哪条边）。

五、MATLAB 示例

例 1：Edmonds–Karp（邻接矩阵残量）

% 容量矩阵 C(u,v)，0 表示无边
n = 6; s = 1; t = 6;
C = zeros(n);
C(1,2) = 10; C(1,3) = 10;
C(2,3) = 2;  C(2,4) = 4; C(2,5) = 8;
C(3,5) = 9;
C(4, t) = 10; C(5,4) = 6; C(5,t) = 10;

residual = C;
maxFlow = 0;
parent = zeros(n, 1);

    function ok = bfs()
        parent(:) = 0;
        vis = false(n, 1);
        q = s; vis(s) = true; parent(s) = -1;
        head = 1;
        ok = false;
        while head <= numel(q)
            u = q(head); head = head + 1;
            for v = 1:n
                if ~vis(v) && residual(u, v) > 0
                    vis(v) = true;
                    parent(v) = u;
                    q(end+1) = v; %#ok<AGROW>
                    if v == t
                        ok = true; return;
                    end
                end
            end
        end
    end

% 为兼容脚本，改用非嵌套实现：
residual = C;
maxFlow = 0;
while true
    parent = zeros(1, n);
    vis = false(1, n);
    q = s; vis(s) = true; parent(s) = -1;
    head = 1; found = false;
    while head <= numel(q)
        u = q(head); head = head + 1;
        for v = 1:n
            if ~vis(v) && residual(u,v) > 1e-12
                vis(v) = true; parent(v) = u; q(end+1) = v; %#ok<AGROW>
                if v == t, found = true; break; end
            end
        end
        if found, break; end
    end
    if ~found, break; end
    % 瓶颈
    add = inf; v = t;
    while v ~= s
        u = parent(v); add = min(add, residual(u,v)); v = u;
    end
    v = t;
    while v ~= s
        u = parent(v);
        residual(u,v) = residual(u,v) - add;
        residual(v,u) = residual(v,u) + add;
        v = u;
    end
    maxFlow = maxFlow + add;
end
fprintf("最大流 = %g\n", maxFlow);

% 最小割：残量上从 s 可达
vis = false(1, n); q = s; vis(s) = true; head = 1;
while head <= numel(q)
    u = q(head); head = head + 1;
    for v = 1:n
        if ~vis(v) && residual(u,v) > 1e-12
            vis(v) = true; q(end+1) = v; %#ok<AGROW>
        end
    end
end
S = find(vis); Tset = find(~vis);
fprintf("最小割 S = "); disp(S);
fprintf("T = "); disp(Tset);
% 割边
fprintf("割边（原容量）:\n");
for u = S
    for v = Tset
        if C(u,v) > 0
            fprintf("%d -> %d : %g\n", u, v, C(u,v));
        end
    end
end

例 2：Dinic 骨架（邻接表）

% 边结构：to, rev, cap
% 此处给最小可运行示例接口
function [maxf, edges] = dinicMaxFlow(n, s, t, edgeList)
% edgeList: each row [u v cap]
    edges = struct("to", {}, "rev", {}, "cap", {});
    g = cell(n, 1);
    function addEdge(u, v, cap)
        edges(end+1).to = v; edges(end).rev = numel(edges)+1; edges(end).cap = cap; %#ok<AGROW>
        edges(end+1).to = u; edges(end).rev = numel(edges)-1; edges(end).cap = 0;
        g{u}(end+1) = numel(edges)-1;
        g{v}(end+1) = numel(edges);
    end
    for i = 1:size(edgeList,1)
        addEdge(edgeList(i,1), edgeList(i,2), edgeList(i,3));
    end
    level = zeros(1, n); it = zeros(1, n); maxf = 0;
    function ok = bfs()
        level(:) = -1; level(s) = 0; q = s; h = 1;
        while h <= numel(q)
            u = q(h); h = h + 1;
            for ei = g{u}
                e = edges(ei);
                if e.cap > 0 && level(e.to) < 0
                    level(e.to) = level(u) + 1; q(end+1) = e.to; %#ok<AGROW>
                end
            end
        end
        ok = level(t) >= 0;
    end
    function fl = dfs(u, f)
        if u == t, fl = f; return; end
        fl = 0;
        for j = it(u):numel(g{u})
            it(u) = j; ei = g{u}(j); e = edges(ei);
            if e.cap > 0 && level(e.to) == level(u) + 1
                ret = dfs(e.to, min(f, e.cap));
                if ret > 0
                    edges(ei).cap = edges(ei).cap - ret;
                    edges(e.rev).cap = edges(e.rev).cap + ret;
                    fl = ret; return;
                end
            end
        end
    end
    while bfs()
        it(:) = 1;
        while true
            pushed = dfs(s, inf);
            if pushed == 0, break; end
            maxf = maxf + pushed;
        end
    end
end

竞赛实现建议：把 Dinic 写成独立 .m 函数文件，便于调试；正文可用 Edmonds–Karp 讲清原理。

例 3：LP 对照

% 小网络用 linprog 验证最大流（变量为每条边流量）
% 省略大规模；思想：max sum leaving s, 守恒, 0<=f<=c

六、如何解释结果

应包含：

1. 网络含义（节点、边、容量单位）；
2. 最大流值；
3. 各边流量表（可只报正流边）；
4. 最小割分区与割边——瓶颈解释；
5. 算法与复杂度；
6. 扩容建议：提高割边容量才能提高最大流。

「当前最大输送 19；瓶颈在割边 2→4 与 5→6……」比只给一个数字有用。

七、常见误区

1. 忘记反向边

无法撤销错误增广，结果可能偏小。

2. 守恒漏点

中间点净流不为 0 则不是可行流。

3. 无向边只建单向

通常建两条有向边，容量各为原容量（视模型而定）。

4. 把最大流当最小费用

无费用目标时算法不优化成本；需最小费用流。

5. 浮点容量死循环

应用整数容量或设残量阈值。

6. 能用最大流却上启发式

标准最大流必须用网络算法或 LP，保证最优。

八、小结

最大流问题的核心思想可以概括为：

在容量约束与守恒条件下最大化源到汇的吞吐；通过残量网络增广（FF/EK/Dinic）求精确最大流，并由可达性给出最小割瓶颈。

它是网络优化的核心模块，也是匹配、割、选址等技巧的跳板。实现时抓住反向边与增广，报告时抓住最小割解释。需要权衡费用时，进入最小费用最大流。