最小费用流的容量逐位缩放

一个容量有三十位，并不意味着应逐单位调整十亿次。容量逐位缩放先解只看最高位的粗问题，每次把旧容量和旧流翻倍，再读入下一位。已有的最优性几乎全部保留：可能破坏势条件的，只是本轮新增加的至多一个单位余量。

形式陈述

先约定核心问题

核心输入是最小费用流的零需求环流问题：每条独立原弧容量 $u_a$ 为非负整数，费用为精确有理数，输出满足所有顶点守恒的最小费用环流及全图可行势。允许自环、平行弧和断开分量，所有容量有限。以下 $m$ 为原弧数， $n$ 为顶点数。

若输入是非零需求，先给出并核验一份整数可行流 $f^0$ ，在它的整个残量网络求零需求最小费用环流 $g$ ，再恢复

f_a=f_a^0+g_{a^+}-g_{a^-}.

正残量方向的容量是 $u_a-f_a^0$ ，反方向是 $f_a^0$ ；两者均为整数，且各保留自己的辅助弧 ID。它们可以同时有正辅助流，但费用相互抵消，恢复后仍有 $0\le f_a\le u_a$ 。任意同需求流也可按差额的正负方向表示为一份辅助环流，因此优化值精确对应。没有可行起点时，先由旧可行性归约求取；不能把需求直接置零，更不能把各点需求独立舍入后假定总和仍为零。

一位容量怎样进入

设当前容量 $u'$ 、流 $f$ 和势 $p$ 已经最优，即全部正残量记录满足 $c_p\ge0$ 。读入下一位 $\beta_a\in\{0,1\}$ 时，先置

u''_a=2u'_a+\beta_a,\qquad \widetilde f_a=2f_a.

旧正向余量变为 $2(u'_a-f_a)+\beta_a$ ，反向余量变为 $2f_a$ 。已有残量方向的费用与势未变；只有原先饱和且新位为一的正向弧，可能新出现负约化费用记录，它的余量恰好为一。

把所有这样的负记录饱和。其反向约化费用为正，故处理完毕后，全图残量费用重新非负；但中间流可能不守恒。定义超额

e(v)=\text{流入}(v)-\text{流出}(v).

$e>0$ 是待送出的积压， $e<0$ 是仍待补足的亏缺。每条新负弧只推一单位，因此总正超额不超过 $m$ 。负费用自环也被送满一单位，却不产生超额。

以最短路修复失衡

选择一个 $e(s)>0$ 的点，在非负约化费用上运行Dijkstra，直到第一个亏缺点 $t$ 被结算。令其距离为 $D=d(t)$ 。与逐次最短路法相同，使用全图截断势更新

p'(v)=p(v)+\min\{d(v),D\},

不可达点也加 $D$ 。只需搜索到 $t$ ：此时所有未结算点的真实距离至少为 $D$ ，取 $D$ 正是所需截断值。沿前驱记录恢复 $s\leadsto t$ 路，推送

\Delta=\min\{e(s),-e(t),\text{路径残量瓶颈}\}.

路径内部净流入不变；起点超额减少、终点亏缺减少，不会产生新的正超额点。路径新反向记录约化费用为零，其他残量记录由截断三角不等式保持非负。反复修复，直到所有超额为零，本位便重新得到最优环流。

为什么必能到达某个亏缺点

倍增后的 $2f$ 本身仍是新容量下的可行环流，因而整轮始终有一份已知可行比较流。对当前伪流 $h$ ，设某正超额点的残量可达集 $S$ 不含亏缺点。所有离开 $S$ 的原弧已经饱和，所有从外部进入 $S$ 的原弧流量为零，否则各自的正向或反向残量记录会离开 $S$ 。于是当前 $S$ 的净流入不大于任何合法环流的净流入零。

可是 $S$ 内没有负超额，且含一个正超额点，其超额和严格为正，矛盾。因此 Dijkstra 必能结算亏缺点。整数流保证每次 $\Delta\ge1$ ，总正超额至多 $m$ ，所以一位至多做 $m$ 次修复。

直觉

倍增旧容量与旧流，不改变哪些旧方向可用，也不改变费用比较。新位造成的困难集中在少量新单位上。先让负约化费用弧立即用满，把“费用不合法”转换成“局部供需失衡”；再用全局非负费用的最短路把这些失衡补平。

修复期间的势已经正确，中间流却未必可行。这与固定流值 SSP 的状态不同：后者每轮有一份当前流值下的可行最优流；这里每次路径更新的目的，是恢复这一容量位阶段的全部顶点守恒。两种状态共用最短路工具，初始化和终止条件需要分别说明。

容量从五的高位逐次读入，每次倍增后只修复新增的负单位残量 — 倍增、读一位、修复失衡

例子与边界

容量五的负二边环

取两条弧 $a\to b$ 和 $b\to a$ ，容量均为五，费用分别为负三和一；目标是零需求最小费用环流。五的二进制是 $101$ 。

已读前缀	容量	倍增后流	新负单位	修复后流	费用
1	$(1,1)$	$(0,0)$	$a\to b$ 推一	$(1,1)$	−2
10	$(2,2)$	$(2,2)$	无	$(2,2)$	−4
101	$(5,5)$	$(4,4)$	$a\to b$ 推一	$(5,5)$	−10

第一位先把负弧送满，超额为 $e(a)=-1,e(b)=1$ 。从 $b$ 出发，沿费用一的 $b\to a$ 补回一单位，势可取 $(p(a),p(b))=(1,0)$ 。第三位开始时旧流变四，新增的 $a\to b$ 余量仍只有一，重复一次修复后流为五。全过程只做两次最短路修复，没有逐单位从零增加到五。

同需求流的恢复必须保留原身份

终结任务从弧 $10:s\to t$ 上的三单位昂贵流出发。辅助网络中的弧 ID $1$ 表示原弧 $10$ 的反向记录，费用负七；最终辅助流沿它送三单位，恢复后原弧 $10$ 的流量才变成零。原弧 $20$ 和 $21$ 虽然都是 $s\to a$ ，费用分别一和二，不能合并为一个未注明费用分段的容量四弧。

这张辅助网络容量最多四，读入三位。各位的总正超额依次是 $0,2,1$ ，实际修复次数为 $0,2,1$ 。辅助最优费用负二十四，加回初始流费用二十一，得到原问题费用负三。这里只报辅助优化费用会少掉那份常数初始费用。

空输入与整数条件

全部容量为零时，没有任何有效位，直接返回零环流和零势；有零费用或正费用自环时，不必送流也可最优。负费用自环独立送满，不应因不改变守恒而遗漏目标贡献。

若容量为 $1/2$ ，逐位读取整数容量的接口不适用。可以把所有容量及初始流乘上公共分母，求解后再缩回，但公共分母的位数和费用恢复必须单独核算。费用本身可以为有理数：本算法的轮数离散性来自容量和超额，不来自费用是整数。

实现成本

令 $L=\lceil\log_2(U+1)\rceil$ ，其中 $U$ 为最大整数容量， $U=0$ 时 $L=0$ 。每位扫描和初始化花 $O(n+m)$ ，至多 $m$ 次 Dijkstra。附件使用允许旧项的二叉堆，最多 $O(n+m)$ 条堆记录，一次搜索、截断势更新与路径恢复为 $O((n+m)\log(n+m+2))$ 。因此总算术次数可保守写为

O\bigl(n+m+L(m+1)(n+m)\log(n+m+2)\bigr),

工作空间为 $O(n+m)$ ，不包含保存全部轨迹的输出。若用带句柄堆，可把对数因子改为 $\log(n+1)$ ，但不能把那个实现的界直接算给附件的懒删除堆。

非零需求的残量环流归约至多产生 $2m$ 条辅助弧，只增加常数倍图规模。恢复原流后，同一份辅助势仍然有效：每个正的原残量方向，必然作为辅助弧的未用正向，或其相反辅助弧已用流的反向出现，所以已被辅助势检查覆盖。输出容量、守恒和约化费用证书的最终检查只需 $O(n+m)$ 。

以上假设精确算术单位成本。容量相关整数为 $O(\log U)$ 位；势和有理费用加法的编码长度也须计入实际位复杂度。逐位缩放消除的是按数值 $U$ 次增广的依赖，不能消除读取这些位本身的代价。

推论与应用

与费用缩放相比，本页固定精确对偶可行性，逐位扩大原始容量；费用缩放保持原始容量，放宽约化费用到 $-\varepsilon$ 后逐步收紧。前者需要整数容量，后者的最终误差门槛需要整数费用。二者名称中的“缩放”不意味着可以混用阶段不变量。

手算迁移：把二边环第二条费用从一改为四。第一位仍可先饱和负弧，但修复会选择其费用三的反向记录，而不走费用四的另一条原弧，最终返回零流。再把容量改为六，按二进制 $110$ 写出每位输入、超额和流量。完整终点给出原始弧与辅助残量 ID 的逐项对应。

参考资料

David Karger，MIT 6.854，Min-Cost Flow，§4.1，PDF p.7：容量逐位倍增、负单位余量与超额修复；本页补全多点亏缺的势和可达性证明。
Stanford CS361B，Advanced Algorithms Lecture Notes，§§3.1–3.2，印刷 pp.16–19：单条容量增加一后的最短路修复、逐位展开。该讲义按弧逐条加一，本页采用一位内先饱和全部负新记录的等价批处理接口。
Andrew V. Goldberg、Eva Tardos、Robert E. Tarjan，Network Flow Algorithms，1990，§5.1 pp.145–146：对偶可行伪流的最短路修复。其 §5.2 采用超额尺度划分，与本页逐位容量实现另行区分。

形式陈述 ​

先约定核心问题 ​

一位容量怎样进入 ​

以最短路修复失衡 ​

为什么必能到达某个亏缺点 ​

容量五的负二边环 ​

同需求流的恢复必须保留原身份 ​

空输入与整数条件 ​

实现成本 ​

反向链接