第26篇用残量网络判断还能不能增加流量。给每条边增加单位费用后，同样大小的流可能有不同总费用；只找到一条增广路，已经不足以决定该走哪条路。最小费用流需要同时维护容量可行性与费用最优性。

本篇采用Bellman–Ford逐次最短增广路。费用可以为负，但初始正容量边组成的全图不得有负费用环；容量、费用和请求流量均为整数。这个条件允许从零流开始证明，不把有限容量的负环误称为无解。

固定流值与最大流值

输入是n个顶点、m条有向边、源s、汇t和请求F。要求n≥2、s≠t、F≥0，容量非负；每条边有独立标识，所以平行边和原生反向边都可以分别计费。教学接口拒绝自环，顶点编号必须落在[0,n)。

输出包括实际流量f、总费用及各原始边流量。先在所有f≤F中最大化f，再在这个流值下最小化费用。若网络能承载F，结果就是所请求流值的最小费用流；若不能，则返回小于F的最小费用最大流。这里没有把“少运一点更便宜”当成可替代目标。

每条边的流量应在0与容量之间。源汇之外的顶点流入等于流出；源的净流出为f，汇的净流入为f。总费用是原始边单位费用乘流量后求和。负边合法，零容量边不能参与当前残量路径或负环。

反向边不仅用于退回容量

原始边u到v费用c，当前流量x、容量a。正向残量边容量a−x、费用c；反向残量边容量x、费用−c。沿反边增广是在撤销原流量，所以费用也必须撤销。

若原图本来还有v到u的边，它的费用和容量属于另一条记录，不能与上述反向残量边合并。实现为每条原始边保存一对残量边编号，通过编号找到反边，避免平行边被端点字典覆盖。

第25篇指出负边不能直接套普通Dijkstra。本实现每轮使用Bellman–Ford，在所有正残量容量边上松弛；前驱只在距离严格改善时更新，不因相等距离反复更换，避免零费用环破坏回溯链。

费用最优性的负环判据

固定流值下，若残量网络含负费用环，可以沿环推送一段正流量。每个顶点在环上流入和流出同时增加，源汇净流量不变，总费用却下降，因此当前流不是最优。

反过来，假设存在同流值但更便宜的可行流。它与当前流的差可以表示为残量网络中的循环流，并分解成若干带非负流量的有向环。总费用差为负，至少一个环费用为负。于是“残量网络没有负费用环”恰好排除了同流值的更便宜方案。

零流的残量网络就是原图的正容量边。因此初始全图无负环使零流已经是流值0下的最优解。只从s检查不够：与s断开的负环也能构成费用更低的循环流，即使F=0也不能忽略。

实现把所有顶点的初始距离设为0，等价于增加一个向每个顶点连接零费用边的超级源。若第n轮仍可松弛，就拒绝初始负环。容量有限时，沿环可推送的量也有限；拒绝表示超出本变体契约，不表示一般最小费用流问题没有有限最优解。

最短增广怎样保持这个判据

设当前残量图无负环，从s可达的顶点集合为R，d(v)是最短距离。对R内部正容量边定义约化费用：

c'(u,v)=c(u,v)+d(u)-d(v).

最短距离满足d(v)≤d(u)+c(u,v)，所以约化费用非负。最短s到t路径的边满足等号，约化费用为0；沿这条路径增广，新增加的反边约化费用也为0。旧边减少容量不会制造负费用环。

还要处理不可达顶点。增广前没有从R到外部的正容量边，否则外部也可达。新反边两端都在R，不会增加跨出的边。含新边的环只能位于R内部，而这里约化费用非负；外部旧环没有变化。约化费用沿环相加时距离项抵消，因此原费用也无负环。

由归纳，每轮之后仍是当前流值下的最小费用流。增广量取路径瓶颈与F−f的较小者，保持容量约束且不超过请求；费用增加量等于增广量乘该路径原费用。

若t不可达，残量图没有s到t路径。第26篇的割论证说明流量不能再增加；结合无负环判据，得到这个最大流值下的最小费用。若已达到F，则直接按固定流值最优性返回。

操作次数不等于输入长度的多项式

正整数残量瓶颈使每次成功增广至少增加1单位流，成功次数至多F，另可能有一次失败的最短路搜索。Bellman–Ford一轮最短路至多n轮边扫描，还需初始化顶点数组；连同初始负环检测，可用O((F+1)n(m+1))作为单位算术模型的保守上界，保存O(n+m)条目。

这是确定性的最坏界，不依赖随机选择，不能标成期望或高概率时间。F以二进制输入只需O(log(F+1))位，所以依赖F的次数界是伪多项式，并不保证对输入编码长度多项式。

整数费用避免浮点相等与负环容差问题，但Python整数运算仍有位成本。若距离、容量与累计费用的中间值最多L位，比较、加法和乘法还要按相应整数成本计费；不能因为增广循环次数受F限制，就把费用的位宽从输入中删去。

势函数和费用缩放的边界

上面的d只是证明工具，本实现没有用势函数加速。另一种实现维护全体残量边非负的约化费用，然后用Dijkstra；必须正确初始化势，并处理更新时不可达顶点，不能只把最短路函数换个名字。

费用缩放允许残量边的约化费用暂时不小于−ε，再逐步减小ε。若最后得到可行流，原费用为整数且ε<1/n，则任意简单环至多n条边，原费用等于约化费用和，大于−1；整数性迫使它非负，于是满足费用最优判据。

这个停止条件解释了整数费用和严格阈值的作用，并没有给出每个缩放阶段的实现或运行时间。本文代码只实现最短增广路，不把缩放算法的复杂度借给它。

运行与反例

接口为min_cost_flow(n, edges, source, sink, requested)，边记录为(u,v,capacity,cost)，返回(flow,total_cost,edge_flows)。整数是教学类型契约，不承担外部文本解析。仓库根目录运行：

1	`python3 examples/advanced-algorithms/check_min_cost_flow.py`

本次退出码为0：500个小图与请求组合、5个边界实例通过，独立枚举共4159个流量向量；8个非法或受限输入被拒绝。边界包含空图、F=0、零容量负边、平行及原生反向边，还有总费用为0的环。

枚举参照给每条原始边尝试0到容量的整数流量，独立检查守恒，再按“流量最大、同值费用最小”排序选答案。它不调用残量最短路，能够发现仅检查容量和费用求和一致仍漏掉的非最优结果。

一个需要撤销旧选择的实例有源0、汇5，所有容量为1。费用为0的边是0→1、0→2、1→3、2→3、3→5、4→5，另有费用1的1→4。先走0→1→3→5后，第二条最短残量路经过3→1反边，将原1→3上的流撤回，再转到1→4→5。实际结果流量2、费用1，原1→3流量为0；若把反边费用或对应关系写错，就不能沿用这条正确性证明。

原始输出保存在writing-plans/advanced-algorithms/evidence/min-cost-flow-results.json。有限枚举验证实现；负环判据与增广不变量才承担一般正确性论证。这里没有测量吞吐、没有实现费用缩放，也没有验证浮点费用。

练习

两顶点间有两条平行边，容量都为1，费用分别为−2和3。请求F=1与F=2时，各边流量和总费用分别是多少？为什么不能按端点合并后只保留一条费用？
在与s、t断开的两个顶点间设置一个总费用为−1、容量有限的环。解释为什么只从s检测负环会漏掉它，以及为什么有限容量使“有负环”不等于“费用无界”。

参考资料

MIT 6.854：Min-Cost Flow：第2–4页负环与约化费用判据，第6–7页最短增广与流值依赖，第8页费用缩放。本文单独保留不可达顶点论证，并使用严格ε<1/n的整数停止条件。