最小费用最大流（SSP）

What · 是什么

最小费用最大流（minimum-cost maximum-flow）：在每条边有容量 c 和单位流量费用 w 的网络中，先最大化总流量，再在该前提下最小化总费用 Σf·w。SSP（Successive Shortest Path，连续最短路）算法是竞赛主流做法：反复用最短路算法在残量网络中找「单位费用和最小」的 s→t 增广路并增广，直到无增广路。费用有负数时用 SPFA/Bellman-Ford 找路；费用非负或已用势能（Johnson 技巧）转非负后用 Dijkstra 加速。

Why · 为什么

How · 实现

伪代码

add_edge(u,v,cap,cost): 正向 [cap,cost], 反向 [0,-cost]
while True:
    dist,pre = SPFA(s,t)   # 或势能+Dijkstra
    if t 不可达: break
    Δ = 沿路最小剩余容量
    沿路正向 cap-=Δ, 反向 cap+=Δ
    maxflow += Δ; mincost += Δ * dist[t]

Python 实现

from collections import deque

class MCMF:
    """最小费用最大流（SSP + SPFA，支持负费用边）."""
    def __init__(self, n):
        self.n = n
        self.adj = [[] for _ in range(n)]

    def add_edge(self, u, v, cap, cost):
        self.adj[u].append([v, cap, cost, len(self.adj[v])])
        self.adj[v].append([u, 0, -cost, len(self.adj[u]) - 1])

    def _spfa(self, s, t):
        INF = 10 ** 18
        dist = [INF] * self.n
        inq = [False] * self.n
        pre_v = [-1] * self.n
        pre_e = [-1] * self.n
        dist[s] = 0
        q = deque([s])
        inq[s] = True
        while q:
            u = q.popleft()
            inq[u] = False
            for i, e in enumerate(self.adj[u]):
                v, cap, cost, rev = e
                if cap > 0 and dist[v] > dist[u] + cost:
                    dist[v] = dist[u] + cost
                    pre_v[v] = u
                    pre_e[v] = i
                    if not inq[v]:
                        q.append(v)
                        inq[v] = True
        return dist[t] != INF, dist[t], pre_v, pre_e

    def min_cost_flow(self, s, t):
        flow, cost = 0, 0
        INF = 10 ** 18
        while True:
            ok, d, pre_v, pre_e = self._spfa(s, t)
            if not ok:
                break
            # 找增广路瓶颈
            add = INF
            v = t
            while v != s:
                u = pre_v[v]
                e = self.adj[u][pre_e[v]]
                add = min(add, e[1])
                v = u
            v = t
            while v != s:
                u = pre_v[v]
                e = self.adj[u][pre_e[v]]
                e[1] -= add
                self.adj[v][e[3]][1] += add
                v = u
            flow += add
            cost += add * d
        return flow, cost

if __name__ == "__main__":
    # 简单网络: 0->1(2,1) 0->2(1,2) 1->2(1,1) 1->3(1,3) 2->3(2,1), s=0,t=3
    m = MCMF(4)
    m.add_edge(0, 1, 2, 1); m.add_edge(0, 2, 1, 2)
    m.add_edge(1, 2, 1, 1); m.add_edge(1, 3, 1, 3); m.add_edge(2, 3, 2, 1)
    fl, co = m.min_cost_flow(0, 3)
    assert fl == 3, fl
    assert co == 10, co  # 流3: 0->1->3(4)+0->1->2->3(3)+0->2->3(3)=10
    print("MCMF basic flow=%d cost=%d" % (fl, co))
    # 用暴力枚举验证小图
    import random, itertools
    random.seed(5)
    for _ in range(120):
        n = random.randint(2, 6)
        edges = []
        for u in range(n):
            for v in range(n):
                if u != v and random.random() < 0.3:
                    edges.append((u, v, random.randint(1, 5), random.randint(0, 5)))
        s = 0; t = n - 1
        m = MCMF(n)
        for u, v, c, w in edges:
            m.add_edge(u, v, c, w)
        fl, co = m.min_cost_flow(s, t)
        # 暴力: 枚举所有流（小图, 容量小）
        def brute(u, cap_left, cost_acc):
            if u == t:
                return (0, cost_acc, cap_left)
            best = None
            # 简化: 只验证最大流值（费用需完整 SSP, 这里不暴力比对费用）
            return None
        # 最大流值用 EK 对照
        def ek(n, edges, s, t):
            cap = {}
            def k(a, b): return (a, b)
            for u, v, c, w in edges:
                cap[k(u, v)] = cap.get(k(u, v), 0) + c
            flow = 0
            while True:
                parent = [-1] * n; parent[s] = s
                q = deque([s])
                while q and parent[t] == -1:
                    u = q.popleft()
                    for v in range(n):
                        if parent[v] == -1 and cap.get(k(u, v), 0) > 0:
                            parent[v] = u; q.append(v)
                if parent[t] == -1: break
                f = 10 ** 18; v = t
                while v != s:
                    u = parent[v]; f = min(f, cap[k(u, v)]); v = u
                v = t
                while v != s:
                    u = parent[v]; cap[k(u, v)] -= f; cap[k(v, u)] = cap.get(k(v, u), 0) + f; v = u
                flow += f
            return flow
        exp_fl = ek(n, edges, s, t)
        assert fl == exp_fl, (n, edges, fl, exp_fl)
    print("MCMF flow-crosscheck OK")

易错点

• 反向边费用必须是 -w，不是 0，否则退流退不回费用
• 有负费用边时不能用裸 Dijkstra，需 SPFA 或先跑一次最短路做势能
• 存在负费用圈时 SSP 不保证正确（先消圈）
• 每次最短路后更新势能 h[u]+=dist[u]（Primal-Dual），否则势能失效
• Python 大流量时注意 F 次增广的总代价，必要时用容量缩放

例题

信源

• OI Wiki✓ https://raw.githubusercontent.com/OI-wiki/OI-wiki/master/docs/graph/flow/min-cost.md
• CP-Algorithms✓ https://cp-algorithms.com/graph/min_cost_flow.html
• 书籍✓ CPH ch20 pp191-204