这份任务对应费用流的改进方向与缩放路线。完成时应交出一份能让别人独立检查的记录：输入身份、起始可行流、三个优化器的实际过程，以及最终容量、供需和费用证书。只报一个最优费用数字还不够。

标准库执行器与完整运行结果可直接下载。运行脚本会把结果写到脚本所在目录；依赖只有 Python 标准库，所有分数使用 Fraction，校验使用显式检查，普通与 python -O 都会执行。题目中 s,a,t,x,y,z 的下标依次为 0,1,2,3,4,5。

一、先交清楚原弧与起点 ​

需求采用“净流入为正”：$b=(-3,0,3,0,0,0)$。原弧如下，自环与平行弧都保留 ID。

ID	起点→终点	容量	费用	初始流
10	$s\to t$	3	7	3
20	$s\to a$	2	1	0
21	$s\to a$	2	2	0
30	$a\to t$	4	1	0
40	$a\to s$	1	0	0
50	$x\to y$	2	−4	0
51	$y\to x$	3	1	0
60	$y\to y$	2	−2	0
70	$t\to a$	1	3	0

逐顶点相加确认需求成立；初始费用是 $3\cdot 7=21$。写出原弧 $10$ 的反向残量记录：方向 $t\to s$、容量三、费用负七。弧 $40$ 本来就是另一条原弧，它不能和某条反向记录因端点相同而合并。

先用最小平均费用环理路最小平均费用环Minimum mean cycle · Minimum cycle mean · Karp minimum mean cycle algorithm用恰好边数的动态规划求最小环均值，再以移权势与紧弧环同时证明下界和可达到性。的小例子熟悉值与证书：完成其五行 DP 表，核四个最大差商 $1,2,-1,-1/2$，再逐弧验证势 $(-3,0,-4,0,0)$ 给出下界负一。为费用二的单点自环另填一张表，说明把“恰好”误写成“至多”会错报均值零。

二、平均环消去：每轮都保持可行 ​

运行最小平均环消去理路最小平均环消去Minimum mean cycle canceling · Minimum mean cycle cancelling · Goldberg–Tarjan cycle-canceling algorithm从任意可行流反复消去最小平均费用残量环，以紧误差收缩和固定弧证明强多项式轮数。。必须记录原弧 ID 和正反符号、均值、瓶颈、更新后的流及费用。四轮答案为：

1. 自环 ${60}^{+}$，均值负二、推两单位，费用 $21\to 17$。
2. ${20}^{+},{30}^{+},{10}^{-}$，均值 $-5/3$、推两单位，费用 $17\to 7$。
3. ${50}^{+},{51}^{+}$，均值 $-3/2$、推两单位，费用 $7\to 1$。
4. ${21}^{+},{30}^{+},{10}^{-}$，均值 $-4/3$、推一单位，费用 $1\to -3$。

每轮应验证 $\mathrm{\Delta }|C|\mu$ 恰好等于费用变化；顶点需求始终不变。说明第三轮为什么不能被“只搜索从 $s$ 可达的区域”替代。再明确区分“这轮记录饱和”与“强多项式证明中的固定弧”，前者本身不能禁止后续反向退流。

三、容量位提升：先确认辅助身份 ​

容量逐位缩放理路最小费用流的容量逐位缩放Capacity scaling for minimum-cost flow · Capacity bit scaling · Bit-scaling minimum-cost circulation从高位到低位读入整数容量，倍增旧流后只修复新单位余量造成的失衡，每位至多 m 次最短路增广。对初始流的残量图求零需求环流。附件以原数组槽位 $i$ 的 2*i 和 2*i+1 作为辅助正反 ID；最终输出仍恢复原 ID。这张图只保留正容量方向，初始辅助 ID 与原方向对应为：

辅助 ID	1	2	4	6	8	10	12	14	16
原方向	${10}^{-}$	${20}^{+}$	${21}^{+}$	${30}^{+}$	${40}^{+}$	${50}^{+}$	${51}^{+}$	${60}^{+}$	${70}^{+}$

辅助最大容量为四，读三位。阶段 bit=2,1,0 的总正超额依次为 $0,2,1$，实际修复次数为 $0,2,1$。第二阶段先饱和辅助弧 $1,10,14$；第三阶段只新增饱和辅助弧 $1$。检查为什么自环辅助弧十四贡献费用，却不贡献总正超额。

最后的辅助流依次为 $(3,2,1,3,0,2,2,2,0)$，辅助费用负二十四。恢复原弧时，辅助 ID 一的三单位必须从初始直达流中减去；其他正方向相加。原总费用是 $21-24=-3$，不能直接把负二十四当作原答案。

另外手算两条容量五、费用负三和一的二边环。把容量改成六后，位串变为 $110$，阶段容量为一、三、六；修复后流依次为一、三、六，只有前两位需要最短路修复，第三位直接倍增。它展示的正是按容量位数推进，而非逐单位增加流量。

四、费用精化：阶段内允许不守恒 ​

运行费用缩放理路最小费用流的费用缩放Cost scaling minimum-cost flow · Epsilon scaling · Goldberg–Tarjan cost scaling逐次减半约化费用误差，以饱和、推送和降势把伪流恢复为可行流，并给出容量数值无关的阶段操作界。，保留六个阶段 $4,2,1,1/2,1/4,1/8$。各阶段末费用为 $17,-2,-3,-3,-3,-3$，Push 次数为 $6,7,3,4,3,5$，Relabel 次数为 $4,6,3,4,3,3$。这些数字取决于附件的输入弧顺序和 FIFO 策略，不是所有合法策略共有的轨迹。

第一阶段开始饱和 ${10}^{-}$、${50}^{+}$、${60}^{+}$，超额变为 $(3,0,-3,-2,2,0)$。逐个核 Relabel 的最大值和 Push 的最小值，至少完成从 $p(s)=0$ 降到负五、沿弧二十推两单位这一段；此时超额 $(1,2,-3,-2,2,0)$ 仍未清零。阶段出口才允许把流当作原需求下的可行流。

附件共做二十八次局部 Push、二十三次 Relabel，当前弧测试一百三十二次；每阶段初始化饱和的工作另由全弧扫描完成，不包含在 Push 计数中。trace=True 保存过程，audit=True 还在每步重查全部 ε 约束和许可图无环；这些教学扫描不能算进仅维护当前弧的核心复杂度。

交一份反例：两点环费用负一和零、零流、势 $(0,-1/2)$，解释 $n\epsilon =1$ 为什么仍未最优。把容量改成三分之一，检查局部推送不再至少为一，但势下降与许可图计数仍有效。

五、最终证书只检查一次，不依赖求解器 ​

三个方法都应给出原 ID 顺序下的流

$$f=(0,2,1,3,0,2,2,2,0),c(f)=-3.$$

逐项核容量和需求，再采用势 $p=(-3,-1,0,0,-1,0)$。最终正残量记录应恰好为：

记录	剩余容量	约化费用
${10}^{+}$	3	4
${20}^{-}$	2	1
${21}^{+}$	1	0
${21}^{-}$	1	0
${30}^{+}$	1	0
${30}^{-}$	3	0
${40}^{+}$	1	2
${50}^{-}$	2	3
${51}^{+}$	1	0
${51}^{-}$	2	0
${60}^{-}$	2	2
${70}^{+}$	1	4

全部非负，所有残量环费用就非负，最优性成立。不同算法可能输出相差常数甚至分量常数的势，逐弧不等式有效即可，不要求势数组逐项等于上表所用势。费用缩放先交付 ε 势，再另做 Bellman–Ford 得到零误差势；容量位提升直接保留其对偶可行势。

六、两项改变结构的迁移 ​

第一项把便宜平行弧二十的容量改为零。先前的三单位直达流仍可行，但两条绕行路径合计只能运两单位，必须保留一单位直达。重算后主运输费用十三、断开环与自环合计负十，最优费用为三；平均环顺序为 ${60}^{+}$、$({50}^{+},{51}^{+})$、$({21}^{+},{30}^{+},{10}^{-})$。交出原始需求不变、瓶颈改变的证据。

第二项保持原容量，把自环六十的费用改成正二。它应保持零流，原来的首轮消失，最终费用变为一。正自环仍要参与证书，不能从输入中无说明地抹掉其 ID。

最后给出输入能力对照：平均环消去接受有理容量与有理费用；容量位提升直接接受整数容量、整数初始流与有理费用；费用 ε 缩放直接接受有理容量与整数费用。需要清分母时写出缩放因子及恢复公式，并把因子的编码长度计入，不能只写“都能处理分数”便跳过算法合同。