最小费用流

最小费用流（minimum-cost flow）在满足容量和流量守恒的所有网络流中，寻找总运输费用最小的一个。它可以固定源汇总流量，也可以给每个顶点指定净供给；若总流量不先固定，而先要求尽可能大再最小化费用，则称最小费用最大流。本文先讲固定源点 $s$、汇点 $t$ 和所需流量 $F$ 的情形。

例如，每条有向边都标有“容量；单位费用”。图中从 $s$ 向 $t$ 运输三单位流量，可先沿 $s\to a\to b\to t$ 送一单位，费用二；再分别沿 $s\to a\to t$ 和 $s\to b\to t$ 送一单位，各费用四，总费用十。问题不仅要构造这样的流，还要证明不存在更便宜的分配。

标签为容量；单位费用。中间的零费用边有容量一，不能把全部流量都送过最便宜路线。

固定流量的数学模型

设有向图 $G=(V,E)$，每条边容量 $u_e\ge 0$、单位费用 $c_e$，变量 $f_e$ 为边流。取“流出减流入”为供给约定，模型为 $$\begin{array}{cc}min& \sum _{e\in E}{c}_e{f}_e,\\ \text{s.t.}& 0\le f_e\le u_e,\\ & \sum _{e\in {\delta }^{+}(v)}{f}_e-\sum _{e\in {\delta }^{-}(v)}{f}_e=b_v(v\in V),\end{array}$$ 其中 $b_s=F,b_t=-F$，其余为零。容量、流量用同一数量单位，费用用“货币／流量单位”，总费用因此用货币计。全体供给之和须为零，因为对顶点守恒式求和时每条边恰好抵消。

主例最终边流按 $sa,sb,ab,at,bt$ 次序为 $(2,1,1,1,2)$。内部点 $a$ 流入二、流出 $1+1=2$；$b$ 流入 $1+1=2$、流出二；源点流出三。费用为 $$2\cdot 1+1\cdot 3+1\cdot 0+1\cdot 3+2\cdot 1=10.$$ 先前的一、四、四是按路线计费，这里是按边计费，两者针对同一条可行流而相等。

反向残量边表示撤销已有选择

对原边 $e:u\to v$，当前流量 $f_e$ 产生两种残量操作：还能增加 $u_e-f_e$ 的正向流，单位增量费用为 $c_e$；也能撤销至多 $f_e$ 的已有流，表示为反向边 $v\to u$，单位增量费用为 $-c_e$。只保留正残量容量的弧，得到残量网络。

反向边不是原模型中新开的一条实际运输线路，而是减少原边流量的记账方式。它可能有负费用，所以即便所有原费用非负，也不能对残量网络直接使用要求非负边权的朴素 Dijkstra 算法。

沿一个残量有向环增加流量，各顶点增加的流入与流出相同，净供给不变；若环的费用总和为负，就得到同一流量下更便宜的方案。因此最优流的残量网络不应含负费用环。

无负环最优性判据。 一个固定供需的可行流最优，当且仅当残量网络没有负费用有向环。

证明。 有负环时，取环上最小残量容量为正增量，就能降低费用而保持可行，故不最优。反过来，设另一个同供需可行流为 $g$。当 $g_e>f_e$，把差额放在正向残量边；当 $g_e<f_e$，把差额的绝对值放在反向残量边。因供需相同，这些非负差额在每点流入等于流出，构成残量环流。

任取一条正差额弧，沿正差额继续走；流量平衡保证进入某点后总有正差额弧离开。有限顶点使路线最终重复顶点，得到一个有向环。沿环减去最小差额，至少一条正差额弧归零；重复有限次，就把差额环流分解成若干个带正权重的环。$g$ 相对于 $f$ 的费用差等于这些环费用乘权重之和。没有负环时每项非负，所以 $g$ 不比 $f$ 便宜，判据得证。

逐次最短增广路的正确性

对于原容量与所需流量均为非负整数、原费用均非负的输入，从零流开始。每轮在残量网络中找费用最小的 $s$ 到 $t$ 路径，沿它增加“不超过路径瓶颈且不超过剩余需求”的最大整数流量，直到达到 $F$。下面解释最短增广不会破坏无负环不变量。

初始残量边费用非负，故没有负环。假设当前也无负环，令 $R$ 为从 $s$ 可达的顶点集，$d(v)$ 为其中各点的最短费用距离。对 $R$ 内每条残量弧 $u\to v$，最短距离定义给出 $$c_{uv}+d(u)-d(v)\ge 0.$$ 这叫作换算后的约化费用。沿最短增广路的弧取等号；增广新产生的反向弧，其约化费用也为零。其他留下的弧仍有非负约化费用，所以 $R$ 内任何环的原费用之和等于其约化费用之和，均非负，因为沿环的距离项相消。

增广新建的反向弧两端都在 $R$ 内；原来不存在从 $R$ 指向外部的正残量弧，现在也不会新增这样的弧。因此新环不可能跨出 $R$ 再返回；完全在外部的网络没有改变。无负环性质得以保持。达到目标流量时，无负环最优性判据便证明结果费用最小。

若尚未达到目标而汇点不可达，所有从 $R$ 指向外部的原边都已饱和，所有反向跨入原边的流量都为零，否则会出现可跨出的残量弧。因此当前净流量等于这个割的容量，任何流都不能更多，要求的 $F$ 不可行。整数容量使每轮至少推进一单位，所以至多 $F$ 轮；这是依赖数值大小的界，并非关于二进制输入长度的强多项式界。

与主例一致的Python实现

输入顶点编号为 $0,\dots ,n-1$，每条边写成 (起点, 终点, 容量, 单位费用)。本实现只接受整数非负原费用、整数非负容量和需求，不接受自环，支持平行弧及原图中的反向弧。返回总费用与按输入次序排列的边流；不改写输入。最短路使用 Bellman—Ford，允许运行中产生的负费用反向弧。

Python 3

def min_cost_flow(n, edges, source, sink, required):
    if not isinstance(n, int) or n < 1:
        raise ValueError("invalid vertex count")
    if source == sink or not (0 <= source < n and 0 <= sink < n):
        raise ValueError("invalid terminals")
    if not isinstance(required, int) or required < 0:
        raise ValueError("invalid demand")
    edges = list(edges)
    graph = [[] for _ in range(n)]
    refs = []
    for u, v, capacity, cost in edges:
        if not (isinstance(u, int) and isinstance(v, int)
                and 0 <= u < n and 0 <= v < n) or u == v:
            raise ValueError("invalid edge endpoints")
        if not (isinstance(capacity, int) and capacity >= 0
                and isinstance(cost, int) and cost >= 0):
            raise ValueError("capacity/cost must be nonnegative integers")
        forward_index, reverse_index = len(graph[u]), len(graph[v])
        graph[u].append([v, reverse_index, capacity, cost])
        graph[v].append([u, forward_index, 0, -cost])
        refs.append((u, forward_index, capacity))
    sent = total_cost = 0
    while sent < required:
        distance = [float("inf")] * n
        parent = [None] * n
        distance[source] = 0
        for _ in range(n - 1):
            changed = False
            for u in range(n):
                if distance[u] == float("inf"):
                    continue
                for i, (v, reverse, capacity, cost) in enumerate(graph[u]):
                    candidate = distance[u] + cost
                    if capacity > 0 and candidate < distance[v]:
                        distance[v] = candidate
                        parent[v] = (u, i)
                        changed = True
            if not changed:
                break
        if parent[sink] is None:
            raise ValueError("required flow is infeasible")
        amount = required - sent
        v = sink
        while v != source:
            u, i = parent[v]
            amount = min(amount, graph[u][i][2])
            v = u
        v = sink
        while v != source:
            u, i = parent[v]
            edge = graph[u][i]
            edge[2] -= amount
            graph[v][edge[1]][2] += amount
            total_cost += amount * edge[3]
            v = u
        sent += amount
    flows = [capacity - graph[u][i][2] for u, i, capacity in refs]
    return total_cost, flows

edges = [(0, 1, 2, 1), (0, 2, 2, 3), (1, 2, 1, 0),
         (1, 3, 2, 3), (2, 3, 2, 1)]
cost, flows = min_cost_flow(4, edges, 0, 3, 3)
assert cost == 10 and flows == [2, 1, 1, 1, 2]
assert min_cost_flow(2, [], 0, 1, 0) == (0, [])
reroute = [(0, 1, 1, 0), (0, 2, 1, 0), (1, 2, 1, 0),
           (1, 3, 1, 1), (2, 3, 1, 0)]
assert min_cost_flow(4, reroute, 0, 3, 2) == (1, [1, 1, 0, 1, 1])
try:
    min_cost_flow(2, [(0, 1, 0, 2)], 0, 1, 1)
except ValueError:
    pass
else:
    raise AssertionError("infeasible demand accepted")
print(cost, flows)

Bellman—Ford 每轮至多扫描 $n-1$ 次全部残量弧；上面按顶点遍历的写法每次成本为 $O(n+m)$。至多 $F$ 次增广，总时间为 $O(Fn(n+m))$，空间为 $O(n+m)$。实际常用势函数配合优先队列改善最短路成本，整数费用很大或流量很大时还会采用其他方法；本实现以完整呈现残量操作为目的。

必须允许撤回的变式

代码中的 reroute 网络有零费用路线 $s\to a\to b\to t$，但每条容量均为一。若先用此路送一单位，第二单位必须走残量路线 $s\to b\to a\to t$：其中 $b\to a$ 撤销先前的 $a\to b$，最终两条实际路线为 $s\to a\to t$ 和 $s\to b\to t$，总费用一。若永久锁定第一次选择而不给反向边，程序会错误报告第二单位无法送达。

只画出变式的第二次增广路。中间的反向弧恢复原边容量，使最终两组运输能够同时完成。

允许负的原费用时，零流的残量图可能已有负环，上面的初始不变量就不成立，不能只取消输入检查便声称算法仍正确。容量无上界且存在可增广的负费用环时，还可能费用无下界；固定流量本身并不排除这个问题。