最小费用最大流

一、直观理解：水要泵得最多，还要电费最省

最小费用最大流（Minimum-Cost Maximum Flow, MCMF）在最大流基础上为每条边增加单位费用 $w(u,v)$：在达到最大流量的所有方案中，选总费用

$$\sum_{(u,v)} w(u,v)\, f(u,v)$$

最小者；也可在给定流量需求 $F$ 下最小化费用（最小费用流）。

直观：不止问「最多能运多少」，还问「运这么多时最便宜的路由组合」。物流、空班指派、供需匹配带成本等，都是它的舞台。

常用算法：在残量网络上反复寻找单位费用最小的增广路（可用 SPFA/Bellman–Ford 处理负权残量边；势函数 + Dijkstra 加速），沿该路增广，直到流量达标或无法增广。

二、适用场景与优缺点

类型	说明
适用场景	带运费的运输、指派问题、带成本的供需平衡、某些调度与循环流；需要同时考虑容量与线性费用。
核心优点	精确最优；比一般 MILP 更贴网络；可输出路径级流量；与最大流、最短路理论统一。
局限与缺点	实现比最大流复杂；负环（费用）需正确处理；非线性费用、固定费用需扩展（常转 MILP）；规模极大时需求精实现。

使用前确认：

1. 费用是否与流量成线性；
2. 要「最大流下最小费」还是「指定流量最小费」；
3. 是否有负费用边（允许但要注意）；
4. 多源汇是否已用超级源汇改造。

三、核心原理

1. 模型

$$\begin{aligned} \min\quad & \sum_{(u,v)} w(u,v) f(u,v) \\ \text{s.t.}\quad & 0\le f(u,v)\le c(u,v) \\ & \text{中间点守恒},\quad \text{净流出}_s=F=-\text{净流出}_t \end{aligned}$$

$F$ 可取最大可能流，即最小费用最大流。

2. 残量上的费用

正向残量边费用 $w(u,v)$，反向残量边费用 $-w(u,v)$（退货退钱）。因此残量网络常含负权，但不能有负费用环（否则可无限循环降费——若容量允许，模型无界）。

3. 连续最短路增广（Successive Shortest Path）

1. 在残量网络中求 $s$ 到 $t$ 的最小费用路径（计费用权）；
2. 按路径残量与剩余需求增广；
3. 更新残量，重复直至需求满足或不可达。

每步增广的是「当前最便宜的增量」，对线性费用可证最终最优。

4. 势函数消负权

维护势 $\pi(v)$，归约费用 $w_\pi(u,v)=w(u,v)+\pi(u)-\pi(v)\ge 0$，从而可用 Dijkstra。$\pi$ 可用上次最短路距离更新。

5. 与 LP / 运输问题

运输问题、指派问题都是最小费用流特例。小规模可用 linprog/matchpairs 验证。

四、关键决策

1. 目标形态

• 固定要运 $F$ 单位：跑到流量 $F$ 停；
• 先最大流再最小费：等价于 $F=F_{\max}$；
• 只最小化费且流量可变化：需看是否有「必须运完」约束。

2. 算法实现难度

教学可用 SPFA 找最短费用路；追求稳可势函数 + Dijkstra。MATLAB 竞赛中，中小规模也可用 LP 建模保证正确。

3. 固定费用

若开边有固定成本，则不是纯 MCMF，应引入 0-1 变量走 MILP。

4. 无界检测

出现负费用环且可增，模型或数据有问题，需检查费用定义。

五、MATLAB 示例

例 1：连续最短路 + Bellman–Ford（清晰版）

% 边：u, v, capacity, cost
edgeData = [
    1, 2, 10, 2;
    1, 3, 8,  5;
    2, 3, 5,  1;
    2, 4, 7,  3;
    3, 4, 10, 2
];
n = 4; s = 1; t = 4;
% 构图：正向 + 反向
m0 = size(edgeData, 1);
to = []; fr = []; cap = []; cost = []; rev = [];
g = cell(n, 1);
function add(u, v, ca, co)
    % 使用工作区数组：在脚本中改为直接追加
end

to = zeros(2*m0, 1); fr = to; cap = to; cost = to; rev = to;
g = cell(n, 1);
eid = 0;
for i = 1:m0
    u = edgeData(i,1); v = edgeData(i,2);
    ca = edgeData(i,3); co = edgeData(i,4);
    eid = eid + 1; e1 = eid;
    eid = eid + 1; e2 = eid;
    to(e1) = v; fr(e1) = u; cap(e1) = ca; cost(e1) = co; rev(e1) = e2;
    to(e2) = u; fr(e2) = v; cap(e2) = 0;  cost(e2) = -co; rev(e2) = e1;
    g{u}(end+1) = e1; g{v}(end+1) = e2;
end
numE = eid;

function [ok, dist, pree] = minCostPath()
    INF = 1e18;
    dist = INF * ones(n, 1); dist(s) = 0;
    pree = zeros(n, 1);
    % Bellman-Ford
    for iter = 1:n-1
        updated = false;
        for u = 1:n
            if dist(u) >= INF/2, continue; end
            for ei = g{u}
                if cap(ei) > 0 && dist(to(ei)) > dist(u) + cost(ei) + 1e-12
                    dist(to(ei)) = dist(u) + cost(ei);
                    pree(to(ei)) = ei;
                    updated = true;
                end
            end
        end
        if ~updated, break; end
    end
    ok = dist(t) < INF/2;
end

maxNeed = inf;  % 最大流意义下：不断增广直到不能
flow = 0; totalCost = 0;
while true
    INF = 1e18;
    dist = INF * ones(n, 1); dist(s) = 0;
    pree = zeros(n, 1);
    for iter = 1:n-1
        for u = 1:n
            if dist(u) >= INF/2, continue; end
            for ei = g{u}
                if cap(ei) > 0 && dist(to(ei)) > dist(u) + cost(ei) + 1e-12
                    dist(to(ei)) = dist(u) + cost(ei);
                    pree(to(ei)) = ei;
                end
            end
        end
    end
    if dist(t) >= INF/2, break; end
    add = maxNeed - flow;
    v = t;
    while v ~= s
        ei = pree(v); add = min(add, cap(ei)); v = fr(ei);
    end
    if add <= 0 || isinf(add)
        % 取路径瓶颈
        add = inf; v = t;
        while v ~= s
            ei = pree(v); add = min(add, cap(ei)); v = fr(ei);
        end
    end
    v = t;
    while v ~= s
        ei = pree(v);
        cap(ei) = cap(ei) - add;
        cap(rev(ei)) = cap(rev(ei)) + add;
        v = fr(ei);
    end
    flow = flow + add;
    totalCost = totalCost + add * dist(t);
end
fprintf("最大流 = %g, 最小总费用 = %g\n", flow, totalCost);

例 2：用线性规划建模（正确性优先）

% 变量：五条原始边的流量 f1..f5（与 edgeData 对应）
% min 2f1+5f2+1f3+3f4+2f5
% 守恒：节点2、3；节点1 净出流 = F, 节点4 净入流 = F
% 先求最大流 Fmax，再在 F=Fmax 下 min cost —— 也可把 F 当变量同时 max 流再分层
c = [2; 5; 1; 3; 2];
% 边:1-2,1-3,2-3,2-4,3-4
% 节点2: f1 - f3 - f4 = 0
% 节点3: f2 + f3 - f5 = 0
% 节点1: f1 + f2 = F
% 节点4: f4 + f5 = F
% 为求最小费用最大流：引入 F，目标 min cost - M*F 或分两阶段
Aeq = [
    1, 0, -1, -1, 0,  0;  % node2
    0, 1,  1,  0,-1,  0;  % node3
    1, 1,  0,  0, 0, -1;  % node1: out - F = 0
    0, 0,  0,  1, 1, -1   % node4: in - F = 0
];
beq = zeros(4, 1);
lb = zeros(6, 1);
ub = [10; 8; 5; 7; 10; 30]; % F 上界宽松
% 两阶段：先 max F
[x1, f1] = linprog([0;0;0;0;0;-1], [], [], Aeq, beq, lb, ub);
Fmax = x1(6);
fprintf("LP 最大流 Fmax = %g\n", Fmax);
% 再 min cost s.t. F = Fmax
Aeq2 = [Aeq; 0 0 0 0 0 1];
beq2 = [beq; Fmax];
[x2, cmin] = linprog([c; 0], [], [], Aeq2, beq2, lb, ub);
fprintf("LP 最小费用 = %g, 流量分配：\n", cmin);
disp(x2(1:5)');

例 3：指派问题作特例

费用矩阵 $n\times n$，每人一任务：可用 matchpairs 或化为二分图单位容量最小费用流。

costMat = [9 2 7; 6 4 3; 5 8 1];
[assign, total] = matchpairs(costMat, 1e6);
disp(assign); fprintf("指派总费用=%g\n", total);

六、如何解释结果

报告：

1. 容量与单位费用含义；
2. 达到的流量 $F$ 与总费用；
3. 各边流量（及可分解的路径流）；
4. 单位流量平均费用；
5. 与「只顾最大流不顾费用」方案的费用对比；
6. 瓶颈：费用高的边是否被绕开、容量低的边是否跑满。

七、常见误区

1. 先随便找一个最大流再局部改费用

不一定全局最优；应用系统 MCMF 或 LP。

2. 残量反向边费用符号错误

必须取相反数，否则费用计算与最优性崩溃。

3. 忽略负环

费用数据错误可能导致算法异常或无界。

4. 固定成本当单位费用

$f>0$ 才收固定费不是 MCMF，需 0-1 开边。

5. 流量未达最大却称「最小费用最大流」

应明确是指定 $F$ 的最小费用流还是 $F_{\max}$。

6. 规模很小时仍只信手写 bug 代码

用 LP 交叉验证是好习惯。

八、小结

最小费用最大流的核心思想可以概括为：

在满足容量与守恒的流中，达到最大流量（或指定流量）的同时最小化线性运输费用；通过残量网络上的最小费用增广逐步构造最优流。

它把最短路与最大流拧在同一框架里，是带成本网络题的精确首选。实现时抓住反向负费用边与增广，报告时给出流量、总费用与路径结构；遇固定费或非线性成本再升级 MILP 或其它模型。