带下界与需求的可行环流

约定与约束 ​

在网络流公理库最大流Maximum flow在容量与流守恒约束下最大化源到汇净流量的问题。的有向边 $e=(u,v)$ 上要求 $l_e\le f_e\le u_e$。本文令节点需求 $b(v)$ 满足

$$\sum _{e\in {\delta }^{-}(v)}{f}_e-\sum _{e\in {\delta }^{+}(v)}{f}_e=b(v),$$

$b(v)>0$ 表示净流入需求，且必要条件为 $\sum _{v}b(v)=0$。

下界消除 ​

先送基础流 $f_e=l_e$，令剩余容量 $u_e^{\prime }=u_e-l_e$。基础流造成的净流入为

$$d_l(v)=\sum _{e\in {\delta }^{-}(v)}{l}_e-\sum _{e\in {\delta }^{+}(v)}{l}_e.$$

剩余流应补足 $r(v)=b(v)-d_l(v)$。若 $r(v)>0$，从超级源 $s^{\ast }$ 向 $v$ 连容量 $r(v)$；若 $r(v)<0$，从 $v$ 向超级汇 $t^{\ast }$ 连容量 $-r(v)$。在原图剩余边上跑最大流，存在可行环流当且仅当 $s^{\ast }$ 的全部出边饱和。

运输例子 ​

合同要求每条指定铁路至少运送 $l_e$ 单位货物。先把这些最低承诺全部送出，会让某些站点净缺货、某些净积压；超级源汇网络检验剩余容量能否恰好补平这些失衡，而不是把下界误当作普通容量上限。

有源汇与费用边界 ​

把有源 $s$、汇 $t$ 的流问题转环流时，常加 $t\to s$ 的无限/目标容量边；是否加入及容量语义必须说明。下界变换只判可行性；最小费用问题还要把基础流常数费用计入，并在残量网络优化。供给/需求正负约定若换向，超级边方向也必须整体换向。

饱和判据证明 ​

若超级源所有出边饱和，删除 $s^{\ast },t^{\ast }$ 后，剩余流在每个原节点恰补足 $r(v)$，加回下界流即满足节点需求和边界。反过来，任意原问题可行流减去下界后给出一份补偿流，可扩展为把所有超级源边饱和的流。因此判据是充要条件，不只是启发式。

总需求不平衡时超级源出容量与入超级汇容量不同，直接无解。无穷容量应实现为不小于所有可能总流的安全上界，并防止整数溢出。

三节点运输的数值变换 ​

设边 $a\to b$ 下界 2、上界 5，边 $b\to c$ 下界 1、上界 4。先送下界后，$a$ 净流出 2，$b$ 净流入 1，$c$ 净流入 1；再结合题目给定的 $b(v)$ 计算每点剩余需求，而不是把这三个数直接当最终超级边容量。

构造完成后应核对三项：所有剩余容量 $u_e-l_e$ 非负，超级源总出容量等于超级汇总入容量，以及最大流值等于该共同总量。任一超级源边未饱和，就能指出一个无法由原图剩余容量补足的节点失衡，形成无解证书。

恢复原流时对每条原边写 $f_e=l_e+f_e^{\prime }$；超级边不属于答案。若容量和需求为整数，最大流整数性给出整数可行环流；实数模型则不能从实现的整数算法无条件继承这一结论。

参考资料

• Ravindra Ahuja, Thomas Magnanti, James Orlin, Network Flows, 1993.
• Jon Kleinberg, Éva Tardos, Algorithm Design, circulation with demands.