基于线性规划的图最小费用循环流问题的多项式时间算法（Minimum Mean Cycle Cancelling）求解示例
1. 问题描述
考虑一个有向图 G = (V, E)，其中每条边 e ∈ E 具有：
- 容量上界 u(e) ≥ 0
- 费用 c(e) ∈ ℝ
- 一个给定的节点供需向量 b(v)，满足 Σ_{v∈V} b(v) = 0
最小费用循环流问题是：
找到一个流函数 f: E → ℝ，满足：
- 流量平衡：对每个节点 v，流入流出量差等于 b(v)，即
∑{(u,v)∈E} f(u,v) - ∑{(v,w)∈E} f(v,w) = b(v) - 容量限制：0 ≤ f(e) ≤ u(e)
- 总费用最小：∑_{e∈E} c(e) f(e) 最小化
这是最小费用流的推广，允许节点有净供应(b(v)>0)或需求(b(v)<0)。
本示例目标：讲解“最小平均费用回路消去算法”（Minimum Mean Cycle Cancelling, MMCC）——一种基于负费用回路检测与消去的强多项式时间算法，用于求解最小费用循环流问题。
2. 算法思想
最小费用流的最优性条件之一是不存在负费用回路（在残留网络中）。
MMCC 算法：
- 从任意可行流开始（可通过添加超级源汇转化为普通最小费用流求得）。
- 重复在残留网络中寻找平均费用最小的负回路（称为最小平均回路），并沿该回路增加尽可能多的流量，以消去该回路。
- 当残留网络中不存在负费用回路时，当前流即为最小费用流。
关键：每次选择最小平均费用的负回路，可保证算法在 O(mn² log n) 或更强的多项式时间内收敛。
3. 算法步骤详解
步骤 1：构建初始可行流
因为问题是循环流（总供应=总需求），可转化为带超级源汇的最小费用流：
- 添加超级源 s，超级汇 t。
- 对每个 b(v)>0 的节点，加边 (s,v)，容量 b(v)，费用 0。
- 对每个 b(v)<0 的节点，加边 (v,t)，容量 -b(v)，费用 0。
- 原图边容量、费用不变。
- 求解 s-t 最小费用最大流（确保所有 b(v) 被满足），得到初始可行流 f。
步骤 2：构建残留网络
对当前流 f，构建残留图 G_f = (V, E_f)：
- 对原边 e = (u,v) 有流量 f(e)，则残留边：
- 前向边 (u,v)：剩余容量 r(u,v) = u(e) - f(e)，费用 c(u,v)。
- 反向边 (v,u)：剩余容量 r(v,u) = f(e)，费用 -c(u,v)。
- 注意：超级源汇的边在初始流满足后不再使用，后续只关注原图节点。
步骤 3：寻找最小平均费用回路
在残留网络 G_f 中，需要找到平均费用最小的回路（允许有向回路重复节点吗？不允许，但算法中通过动态规划可处理）。
最小平均回路定义：
回路 C 的平均费用 = (∑_{e∈C} c(e)) / |C|
目标：找到平均费用最小的回路（可能是负的）。
寻找方法：可用 Karp 的“最小平均回路算法”：
- 令 d[k][v] = 从任意起点到 v 恰好经过 k 条边的最小费用路径（允许重复边）。
- 用动态规划计算 d[k][v] 对 k=0..n, v∈V。
- 对每个节点 v，计算 min_{0≤k≤n-1} (d[n][v] - d[k][v]) / (n - k)，其最小值即为最小平均费用 λ*。
- 通过回溯找到对应的回路。
复杂度 O(mn)。
步骤 4：沿回路增流
找到最小平均负费用回路 C 后（λ* < 0）：
- 令 Δ = min_{e∈C} r(e) 为该回路上的最小剩余容量。
- 对 C 中每条前向边 e，增加流量 Δ；对反向边 e，减少流量 Δ。
- 更新残留网络。
步骤 5：检查最优性条件
如果残留网络中不存在负费用回路（即最小平均费用 ≥ 0），则当前流 f 是最小费用循环流，算法终止。否则回到步骤 3。
4. 示例演算
考虑简单图：V={1,2,3,4}，边与数据如下：
| 边 (u,v) | 容量 u | 费用 c | 节点供需 b(v) |
|---|---|---|---|
| (1,2) | 5 | 2 | b(1)=4 |
| (2,3) | 3 | 1 | b(2)=0 |
| (3,4) | 4 | 3 | b(3)=-4 |
| (4,1) | 6 | -4 | b(4)=0 |
| (2,4) | 2 | 2 |
步骤1：构造超级源 s 和汇 t，加边 (s,1): 容量4，费用0；(3,t): 容量4，费用0。求 s-t 最小费用最大流（可用 SSP 算法），得到一个可行流：
f(1,2)=4, f(2,3)=3, f(2,4)=1, f(3,4)=3, f(4,1)=4，其他为0。满足 b。
步骤2：构建残留网络（只考虑原图节点1,2,3,4），残留边：
- (1,2): 剩容量1，费用2
- (2,1): 容量4，费用-2
- (2,3): 剩容量0，费用1；反向(3,2): 容量3，费用-1
- (3,4): 剩容量1，费用3；反向(4,3): 容量3，费用-3
- (4,1): 剩容量2，费用-4；反向(1,4): 容量4，费用4
- (2,4): 剩容量1，费用2；反向(4,2): 容量1，费用-2
步骤3：在残留网络中找最小平均费用回路。
候选回路1：C1 = 1→2→4→1，费用=2+2+(-4)=0，平均0。
候选回路2：C2 = 1→2→4→3→4→1? 不行，节点重复。
用 Karp 算法计算：
实际上，可以枚举简单回路。找到回路 4→3→2→4? 残留边：(4,3) 容量3费用-3, (3,2)容量3费用-1, (2,4)容量1费用2，总费用=-2，长度3，平均 ≈ -0.667。
还有更小的吗？检查回路 4→1→2→4: (4,1):-4, (1,2):2, (2,4):2，总费用0。
回路 1→2→4→3→4→1? 不简单。
但已知 4→3→2→4 是负回路，且可能是最小平均的（通过 DP 验证）。
步骤4：沿 C=4→3→2→4 增流，Δ = min{r(4,3)=3, r(3,2)=3, r(2,4)=1} = 1。
更新流量：
f(4,3) 增加1（原反向边减少1等价于正向边增加1），
f(3,2) 增加1，
f(2,4) 增加1。
更新后：f(4,3)=原来的反向流量3变成正向1? 我们需明确：原流中(3,4)=3, 所以残留(4,3)容量3。增流1后，意味着从4到3流1，即原(3,4)减少1变为2，同时(2,4)从1增加为2，(3,2)从反向流变为正向流1。
重新计算平衡：节点4：入=2（从2来）+? 出=1（到3）+? 需仔细，但算法自动保持平衡，因为回路增流不影响节点净流量。
更新后费用变化：Δ * (-2) = -2，总费用减少2。
步骤5：重新检查残留网络，继续找最小平均回路，直到无负回路。
5. 算法复杂度与收敛性
- 每次消去最小平均回路，可以使势函数的某个度量改进，Goldberg 和 Tarjan 证明迭代次数为 O(mn log n) 或 O(mn² log n)（取决于实现）。
- 每次找最小平均回路 O(mn)，总复杂度 O(m²n² log n) 或更好。
- 是强多项式时间算法，不依赖于费用值的大小。
6. 总结
最小平均费用回路消去算法是一种优雅的强多项式时间算法，用于最小费用循环流问题。其核心在于利用最小平均负回路的选择，保证了较快的收敛速度。该算法体现了线性规划中对偶理论（最优性条件对应无负回路）与组合优化中回路消去技术的结合。