最小平均环消去 | Codeboy's Blog

已经满足供需的运输方案仍可能太贵。沿一个负残量环调整流量，能降低费用且不改变任何站点的净需求；问题在于每次选哪个环。最小平均环消去始终选择每条弧平均费用最负的环。这个选择不仅影响眼前省多少钱，还使剩余误差按可证明的速度收缩。

形式陈述

一轮操作与终止证书

沿用最小费用流的有限容量、有身份弧记录及需求约定。输入还包括一份已核验容量与供需的可行流 $f$ 。本页处理费用优化；没有可行起点时，先做可行性归约，不能把任意零流冒充满足非零需求的流。

对每条正残量记录，以正向费用 $c_a$ 或反向费用 $-c_a$ 建图，求最小平均费用环 $C$ ，记均值为 $\mu$ 。

若无环，或 $\mu\ge0$ ，停止并输出 $f$ 与全残量非负约化费用势。
若 $\mu<0$ ，令 $\Delta$ 为环上残量容量的最小值，沿该环推送 $\Delta$ ；正记录增加原弧流，反记录减少原弧流。
重新建立残量图，继续求最小均值。

$\Delta>0$ ，至少一条环记录饱和。容量和所有顶点的需求保持不变，真实费用减少 $-\Delta|C|\mu>0$ 。终止时无负残量环，旧模型的最优性判据给出全局最优性。下面证明这个过程在精确实数算术下也只需多项式次操作，而不依赖“每次费用至少下降一”。

误差取可实现的最小值

称可行流 $f$ 为 $\varepsilon$ -最优，如果存在势 $p$ ，使每条正残量记录满足

c_p(u,v)=c_f(u,v)+p(u)-p(v)\ge-\varepsilon.

定义 $\varepsilon(f)$ 为这种非负误差的最小值。有负环时

\varepsilon(f)=-\mu_*;

没有负环时为零。必要性来自沿环求和；充分性把每条残量费用加上 $\varepsilon$ ，在无负环的移权图求最短势。这里“最优误差”指对所有势取最小，不是随便给出的一个宽松上界。[1，§4.2]

若 $\varepsilon(f)>0$ ，取达到这个下界的势。最小平均环上各弧约化费用至少为 $-\varepsilon(f)$ ，其平均值又正好等于它，故每条弧都等于 $-\varepsilon(f)$ 。推送后新出现的反向记录费用为 $+\varepsilon(f)$ ，其余记录保持原下界，所以

\varepsilon(f_{\mathrm{new}})\le\varepsilon(f).

每 m 轮至少收缩一次

设原网络有 $m$ 条有身份弧， $n\ge2$ 个顶点。固定一轮起点的紧误差 $\varepsilon>0$ 及其势 $p$ ，在接下来的一批操作中不改变这份分析用势。每对正反残量记录的约化费用互为相反数，因此初始负约化费用记录至多 $m$ 条。

只要所消去的环全由这份固定势下的负记录组成，每轮至少删去其中一条，并且只产生正费用反向记录。若连续 $m$ 轮都如此，负记录已耗尽，当前流最优。

否则，考虑第一次选中的环含有非负约化费用记录。此前出现的全部残量记录仍满足 $c_p\ge-\varepsilon$ ；该简单环长至多 $n$ ，且至少一项非负，所以其平均费用至少为

-\frac{n-1}{n}\varepsilon.

因为选中的确实是当前最小平均环，此时紧误差已不超过 $(1-1/n)\varepsilon$ ，之后又不会增大。两种情况合起来证明：每 $m$ 次消去，要么终止，要么紧误差至多乘上 $1-1/n$ 。[1，Lemma 4.5.1]

直觉

“至少饱和一条弧”本身不能限制总轮数：一条弧以后可能沿反向退流，再次变得可用。真正有效的记账分两层。短期固定势，看负约化费用记录怎样被消耗；长期让紧误差足够缩小，把某条弧的流量固定到以后所有更精确解都必须采用的值。

算法执行时只要求每轮找到最小平均环，不需要显式维护下面证明中的“固定弧集合”。固定性是一份终止分析证据，不是未经检查便把容量边删除的实现指令。

例子与边界

同时修正主运输路线和断开环

六顶点中的五个记为 $s,a,t,x,y$ ，第六个孤立。初始在容量三、费用七的弧 $10:s\to t$ 上送三单位，费用为二十一。其他弧初流为零：

ID	弧	容量	单位费用
20	$s\to a$	2	1
21	$s\to a$	2	2
30	$a\to t$	4	1
40	$a\to s$	1	0
50	$x\to y$	2	−4
51	$y\to x$	3	1
60	$y\to y$	2	−2
70	$t\to a$	1	3

以下 $a^+$ 、 $a^-$ 分别表示原弧的正向、反向记录。附件得到四轮：

轮	最小平均环	均值	瓶颈	更新后总费用
1	$60^+$	−2	2	17
2	$20^+,30^+,10^-$	−5/3	2	7
3	$50^+,51^+$	−3/2	2	1
4	$21^+,30^+,10^-$	−4/3	1	−3

第二轮把两单位昂贵直达流改走便宜路径，费用减少 $2\cdot5=10$ 。第三轮与源汇完全断开，却仍降低总费用。第四轮使用另一条平行弧，说明只按端点合并记录会漏掉容量与费用的区别。

最终按 ID $10,20,21,30,40,50,51,60,70$ 排列的流为

f=(0,2,1,3,0,2,2,2,0).

势 $p=(-3,-1,0,0,-1,0)$ 使全部正残量记录约化费用非负。主运输费用七，断开二边环费用负六，自环费用负四，总费用为负三。

为什么饱和过的弧仍会回来

两条同向平行弧费用不同，可以先沿较贵弧送流，再沿较便宜弧和贵弧的反向记录组成环，把旧流撤回。一次饱和只说明该轮的瓶颈，不能推出该弧以后永远固定。下节的固定弧条件涉及约化费用相对当前误差的比例，要求更强。

若费用全非负，零需求的零流已最优；非零需求的任意可行流则仍可能通过反向残量记录改便宜。若仅有一个顶点，各自环互不影响，负费用自环分别送满，至多 $m$ 轮即可；不必套用含 $1-1/n$ 的一般分组证明。

推论与应用

从误差收缩到强多项式轮数

先证明固定弧引理。若 $f$ 对势 $p$ 为 $\eta$ -最优，且某原弧满足 $|c_p(a)|>2n\eta$ ，则该弧在所有 $\eta$ -最优可行流中的流量相同。以 $c_p(a)>2n\eta$ 为例：若 $f_a>0$ ，反向残量费用小于 $-\eta$ ，矛盾，因此 $f_a=0$ 。

设另一份 $\eta$ -最优流 $g$ 在这条弧上有正流。差额 $g-f$ 按正反方向形成非负残量环流。由流分解定理，这条增加的弧位于其中一个简单环上；其余至多 $n-1$ 条记录在 $f$ 的残量图中，约化费用均不小于 $-\eta$ 。整个环费用严格大于

2n\eta-(n-1)\eta>n\eta.

把这条环反向，它属于 $g$ 的残量图，长度至多 $n$ 而费用小于 $-n\eta$ ，与 $g$ 的 $\eta$ -最优性矛盾。负号情形交换正反方向，得到该弧必须一直在上界。[1，Corollary 4.3.2]

现在把操作分成每组 $O(mn\log(n+1))$ 轮。收缩引理保证：若一组结束时尚未终止，紧误差已从组首的 $\varepsilon$ 减为 $\eta<\varepsilon/(2n)$ 。组首所消去的环均值为 $-\varepsilon$ ；在组尾任何达到紧误差的势下，环费用总和不变，所以其中至少一条记录约化费用不大于 $-\varepsilon<-2n\eta$ 。

固定弧引理说明该原弧在此后所有更小误差的流中都不会再变化；但它确实在本组第一轮被改变过，所以不能是以前各组已经固定的弧。每组至少固定一条新原弧，总组数至多 $m$ 。因此消去次数为

O\bigl(nm^2\log(n+1)\bigr).

结合一次最小平均环的 $O(n+m+nm)$ 算术次数，去除全程不参与运算的孤立点后可写总时间 $O(n+m+n^2m^3\log(n+1))$ ，空间 $O(n+m+n^2)$ 。这是精确实数算术下不依赖容量、费用大小的组合操作界；有理数实现还要计入中间数的位成本，不能据此声称任意大整数加法都是常数时间。[1，Theorems 4.5.3–4.5.4]

整数费用另有较短界：起始误差至多 $C=\max_a|c_a|$ ，误差小于 $1/n$ 时每个简单环费用大于负一，只能非负。因此消去次数也不超过 $O(mn\log(nC+2))$ 。容量无需为整数；这条终止门槛用的是费用的整数性。

输出能力与代价边界

在有负原费用、断开分量或任意同需求可行起点时，本算法仍可直接进入优化。它保持每轮流可行，适合逐次保存可验证的改进记录。另一方面，每轮重新计算全图最小均值开销很大；费用缩放等算法可以采用便宜的局部操作，但必须重新证明中间伪流状态及 ε 约束。

手算迁移：把弧 $20$ 的容量从二改为零，不改变初始直达流，写出剩余的平均环顺序和最终费用；再把自环费用改为正二，说明哪一轮消失、最终证书应怎样调整。完整终点同时对照三种优化器及可独立核验的最终势。

参考资料

Andrew V. Goldberg、Eva Tardos、Robert E. Tarjan，Network Flow Algorithms，1990，§4.2 pp.137–139、§4.3 pp.139–140、§4.5 pp.142–144：紧误差、固定弧、每 m 轮收缩与强多项式消去界。
Andrew V. Goldberg、Robert E. Tarjan，Finding Minimum-Cost Circulations by Canceling Negative Cycles，Journal of the ACM 36(4)，1989，pp.873–886，DOI。最小平均环消去方法的原始论文。
Ankur Moitra，MIT 6.854/18.415，Lecture 9，2016，§2.2 pp.2–4：均值下界与势、整数费用的收缩分析；强多项式固定弧论证采用上列作者重印本。

形式陈述 ​

一轮操作与终止证书 ​

误差取可实现的最小值 ​

每 m 轮至少收缩一次 ​

同时修正主运输路线和断开环 ​

为什么饱和过的弧仍会回来 ​

从误差收缩到强多项式轮数 ​

输出能力与代价边界 ​

反向链接