最小费用流的费用缩放

某条弧约化费用为负，表示按当前价格把流送过去有利。先全部送满，把这种局部有利选择变成各站点的积压与亏缺。活跃点只沿仍有利的方向搬运；无路可搬时，就降低自己的价格，直到至少打开一条许可出路。

降势并不是无界地“降到能走为止”。后面的比较流论证给出每个阶段的总降幅上限，许可图的无环性再控制小推送的次数。因此容量即使有很大分母，算法也不靠每次至少搬动一单位来终止。

图中只画局部的弧 $20,30,10$；平行弧 $21$ 与断开分量仍参与执行器计算。边旁标的是残量 ID 与约化费用，最后一格的反向弧表示本次推送新产生的两单位余量。

一个局部放电可以手算 ​

终结任务初始在 $s\to t$ 上送三单位、费用七。第一阶段 $\epsilon =4$，先沿其反向残量记录退回三单位，于是 $e(s)=3,e(t)=-3$。此时 $s\to a$ 有费用一、容量二的弧 $20$，以及费用二、容量二的平行弧 $21$；$s\to t$ 的正向费用仍为七。

零势下没有负出弧，所以对 $s$ 降势：三个候选依次为 $-1-4=-5$、$-2-4=-6$、$-7-4=-11$，最大值为负五。降势后，弧 $20,21,10$ 的约化费用依次是 $-4,-3,2$。沿 $20$ 推两单位，得到 $e(s)=1,e(a)=2,e(t)=-3$。这仍是伪流，不能因为找到有利路径就结束。

同一实例的六个完整阶段 ​

执行器按输入弧次序扫描，活跃点用 FIFO 队列，结果如下。这里 Push 不包括阶段开头的饱和操作。

六点满足 $6\cdot (1/8)<1$，此时才由整数费用门槛自动证明最优。虽然第三阶段已经碰到最优费用，算法并不知道这一事实，仍继续收紧。第一阶段甚至把退回的直达流重新送上直达弧，只保留负自环收益；这不违反误差合同，也不要求每个局部操作都降低原始费用。

零费用自环不能决定 Relabel ​

两点环有 $s\to t$ 费用一百、$t\to s$ 费用负一百零一，容量均一；另有 $s$ 的零费用自环，初始流为零。阶段误差六十四，先饱和负弧，得到 $e(s)=1,e(t)=-1$。正确 Relabel 在非自环候选 $-164,-165$ 中取 $-164$，立即打开约化费用负六十四的 $s\to t$。若纳入零自环的伪候选 $p(s)-64=-64$，降势后自环仍为零，其他出弧仍为正，便违反“一次降势打开一条许可弧”的合同。附件把这项作为显式回归。

等号处确有负环 ​

两点环的弧费用为负一和零，容量均一，取零流、势 $(0,-1/2)$。两条正残量记录约化费用都是 $-1/2$，所以 $\epsilon =1/2$ 合法，且 $n\epsilon =1$。但整个环费用仍为负一，可以送一单位改善。终止判断必须严格，不能写成 $n\epsilon \le 1$。

若费用改为任意有理数，即使 $n\epsilon <1$ 仍可能存在费用 $-1/100$ 的环。可先清除费用分母后用整数门槛，但阶段数要按清分母后的费用位长计算。若用浮点容差代替严格负号，许可图、精确饱和及最优证书都需要重新解释，本页执行器拒绝浮点输入。

为什么每点只能降势 O(n) 次 ​

固定本阶段入口的可行流 $\overline{f}$ 和势 $\overline{p}$，它们满足 $2\epsilon$ 约束。任一时刻，当前伪流 $f$ 的正超额点 $v$ 都能通过“把 $f$ 改回 $\overline{f}$”的差额支撑，到达一个负超额点 $w$。选择简单路径 $P$，长度 $\ell \le n-1$。路径正方向属于当前残量图，反方向属于 $\overline{f}$ 的残量图：

亏缺只在阶段初始化产生；Push 的源始终非负，接收端超额只会增加。因此一个此时仍亏缺的 $w$ 从未成为活跃点，也从未降势，$p(w)=\overline{p}(w)$。相加得到

每次 Relabel 至少降低 $\epsilon$，所以每点每阶段至多 $3(n-1)$ 次。这个界以当前正超额和入口可行比较流为基础，与容量大小无关。[1，Lemmas 3.4.4–3.4.6]

推送次数怎样支付 ​

同一记录方向两次饱和 Push 之间，必须先沿反方向退流；退流要求反方向费用为负，正方向因此为正。要重新沿正方向 Push，只有尾点进一步降势才可能使其再次为负，邻点降势只会让该方向费用增加。因此饱和 Push 总共 $O(nm)$ 次。

非饱和 Push 会把源点超额清零，却不删除许可弧。用势能法理路势能法Potential method用数据结构状态势函数的增量调整单步记账，以控制操作序列的总成本。，令 $R(v)$ 为许可图中从 $v$ 可达的顶点数，计入 $v$ 自身；取势能为所有活跃点的 $R(v)$ 之和。许可图无环，沿 $u\to v$ 有 $R(u)\ge R(v)+1$。一次非饱和 Push 移除活跃源 $u$，至多增加活跃终点 $v$，所以势能至少减少一。

饱和 Push 至多新激活一个点，使势能增加至多 $n$。Relabel 后无人能经许可弧进入被改标点，其他点的可达集不能增加；只有该点的项可能增加，增幅至多 $n$。结合 $O(n^2)$ 次 Relabel 和 $O(nm)$ 次饱和 Push，非饱和 Push 总数为 $O(n^2(m+n))$。[1，Lemma 3.4.8]

当前弧、初始化和位成本 ​

附件为每个顶点保存当前邻接位置。检查失败后向后推进，只有本点 Relabel 才重置；邻点降势会使该出记录费用增加，反向 Push 新开的出记录费用为正，所以跳过的记录不会无故变成新的许可弧。每个阶段所有邻接重扫和 Relabel 的取最大值扫描共 $O(nm+n)$，加上实际 Push 和 FIFO 管理，时间为 $O(n^2(m+n)+n+m)$。

共需 $O(1+\log (nC+2))$ 个阶段。最终的 ε 势未必让每条残量费用非负；若要交付旧模型的零误差势证书，再用一次全图Bellman–Ford理路Bellman–Ford 算法Bellman–Ford algorithm通过反复松弛边求含负权边图的单源最短路并检测可达负环。求势，计入 $O(n+nm)$。总工作空间为 $O(n+m)$；保存逐操作超额快照的 trace=True 另付每次 $O(n)$ 输出，audit=True 每步扫描全残量图并检查许可图无环，均不计入核心运算界。

整数费用和二分误差使势为二进制有理数，阶段内总降幅受上界控制。容量若为有理数，可以统一分母理解流和超额的编码长度；精确加减、比较与最小值的位成本仍须另计。上述操作界不依赖容量的数值或分母，不等于对任意长度输入都只花常数位操作。

与容量缩放的选择边界 ​

容量逐位缩放理路最小费用流的容量逐位缩放Capacity scaling for minimum-cost flow · Capacity bit scaling · Bit-scaling minimum-cost circulation从高位到低位读入整数容量，倍增旧流后只修复新单位余量造成的失衡，每位至多 m 次最短路增广。始终维护精确非负约化费用，通过容量位数限制修复总量；本页保持原容量，通过费用位数限制 ε 阶段，阶段内部的流可以有任意正负超额。已有整数容量但有理费用时，前者可直接运行；有理容量但整数费用时，后者可直接运行。

手算迁移：在两点门槛反例中把容量都改成 $1/3$，比较“每次至少推一单位”为什么失效，而本页的降势和许可图计数为何仍成立。随后运行终结任务，给出全部阶段末的容量、守恒和误差检查，不能只报最后的费用数字。