上下界网络流 · 可行流

上下界网络流

到目前为止，每条边的约束都是 ${0 \le f(e) \le cap(e)}$ ——流量只有上限。但很多现实问题还要求每条边至少跑多少：一条骨干链路必须承载基础流量、一台机器一天至少处理若干订单、一条排班必须覆盖最低人手。这就是带下界的流 (flows with lower bounds)：给每条边一个下界 lower(e) 与上界 upper(e)，要求 $lower(e) \le f(e) \le upper(e)$ 。本页用构造与推导把这类约束一步步化归回普通最大流。

1 · 下界为什么棘手

普通最大流里，「全零流」 $f \equiv 0$ 永远是一个合法起点，算法从它出发不断增广即可。一旦每条边有了正下界，全零流通常就不再合法——它违反了下界约束。更麻烦的是：强行把每条边先填到它的下界 lower(e)，得到的「流」几乎一定破坏流量守恒：某个点流入的下界之和与流出的下界之和并不相等，凭空多出或缺了一截。

核心拆解： 把每条边的流量写成 f(e) = lower(e) + g(e)，其中 $g(e) \in [0, upper(e) - lower(e)]$ 是一段普通的、从 0 起算的流。这样下界被「分离」了出来：g 是我们真正要求解的对象，而 lower 部分是固定的「底流」。代价是 lower 这部分底流破坏了守恒，必须在每个点把它补偿回来。

思路一句话： 先在每条边铺上它的下界（承认守恒被破坏），再用一套超级源 / 超级汇把每个点的盈亏「填平」。能填平 ⟺ 存在可行流。填平之后，叠加在底流上的 g 就是普通最大流能解的部分。

2 · 无源汇可行流 (circulation with lower bounds)

先看最纯粹的版本：图里没有源也没有汇，要求每个点都流入 = 流出（整张图是一组环流 circulation），且每条边满足 $lower \le f \le upper$ 。问：这样的可行 circulation 是否存在？

第一步 · 铺下界，算每点盈亏。 令每条边先承载 lower(e)。定义节点 v 的盈亏 (excess):

d(v) =（流入 v 的边下界之和）−（流出 v 的边下界之和）= Σ_{e 入 v} lower(e) − Σ_{e 出 v} lower(e)

d(v) > 0 表示「底流让 v 多收了 d(v)」，需要把这些多出来的导走；d(v) < 0 表示「底流让 v 少收了 |d(v)|」，需要从别处补进来。所有 d(v) 之和必为 0（每条边的下界既被它的终点 +1 次、又被它的起点 −1 次）。

第二步 · 建超级源 ss、超级汇 tt，把盈亏接出去。

其一每条原边 $u\to v$ 的容量改为 $upper - lower$ ——这正是 g(e) 的活动范围；

其二对 d(v) > 0 的点，连一条 $ss \to v$ ，容量 d(v)——把多出的流量「排走」；

其三对 d(v) < 0 的点，连一条 $v \to tt$ ，容量 $-d(v)$ ——给缺的流量「补口」。

原图里下界全部归零，守恒缺口集中由 ss / tt 这一圈附加边承担。

第三步 · 在新网络上跑 $ss \to tt$ 最大流，看附加边是否全部满流。

判定： 设所有正盈亏之和 D = Σ_{d(v)>0} d(v)（= 所有负盈亏绝对值之和）。若 $ss \to tt$ 的最大流恰为 D——也就是每条附加边都满流——则原问题存在可行 circulation，且 f(e) = lower(e) + g(e)，其中 g(e) 取新网络上该原边的流量。若最大流 < D（存在未满的附加边），则无可行流：某处的下界缺口无法被填平。

为什么「附加边满流」恰好对应「守恒被填平」？因为附加边满流意味着每个 d(v) > 0 的点都把多出的 d(v) 全部经 ss 排走、每个 d(v) < 0 的点都从 tt 补满 |d(v)|。把这些「排走 / 补进」与底流叠加，每个点的净收支正好归零——守恒恢复，得到一组合法 circulation。

3 · 有源汇可行流：加一条 t→s 的 ∞ 边

现在回到带源 s 与汇 t 的常规设定：要求一个满足所有上下界的 $s\to t$ 流（s、t 不必守恒，中间点守恒）。一个简洁的化归：从汇 t 向源 s 连一条边 $t \to s$ ，下界 0、上界 ∞。

加上这条边后，s 流出的量会经由 $t \to s$ 原样绕回，于是 s 和 t 也满足了守恒——整张图变成一个无源汇的 circulation。这样就完全套用上一节的方法：算各点 d(v)、建 ss / tt、跑最大流、查附加边是否全满。

那条 t→s 边承载多少？ 它的流量 $f(t\to s)$ 正好等于原问题里 $s\to t$ 的流值 |f|——因为绕回 s 的量必然等于 s 净送出去、最终抵达 t 的量。求出可行 circulation 后，删掉这条 $t\to s$ 边读回的就是一个合法的有源汇可行流。

4 · 有源汇最大流 / 最小流

可行流只是「能跑通」的任意一个解。要在满足下界的前提下把 $s\to t$ 流值顶到最大（或压到最小），分两个阶段：先求任一可行流，再在残量网络上调整。

有源汇最大流：

按上一节加 $t\to s$ (∞)边，求出一个可行 circulation，确认所有附加边满流。
把 ss、tt 以及它们的附加边、还有那条 $t\to s$ 边全部删除，只保留原图的残量网络（各原边残量 = $upper - f$ ，反向边残量 = $f - lower$ ）。
在这张残量网络上，从 s 到 t 再跑一次普通最大流，把增广得到的流值累加到可行流的流值上。每条增广路只会在 [lower, upper] 区间内调整，下界自动不被破坏。

最终 有源汇最大流 = 可行流流值 + 第二阶段 $s\to t$ 增广量。反向边残量 $f - lower$ 保证回退时不会把某条边压到下界以下。

有源汇最小流： 对称地处理——求出可行流后，在去掉附加结构的残量网络上从 t 到 s 跑增广（等价于沿 $s\to t$ 方向退流），把能退回的量从可行流流值里减去，即得满足所有下界的最小可行流值。

实现上常用的等价写法： 先不加 $t\to s$ 边求一遍 $ss\to tt$ 最大流；再加入容量 ∞ 的 $t\to s$ 边、继续增广至 $ss\to tt$ 饱和；此时 $t\to s$ 边上的流量即最小流（最大流则在第二阶段改为从 s 到 t 增广取最大）。原理与上面分阶段叙述完全一致，只是把两步合进同一张残量网络。

5 · 完整数值例子：一张可行 circulation

取一张无源汇的小网，三个点 $a \cdot b \cdot c$ ，四条带 [lower, upper] 的边。逐列算出 cap' = upper − lower、各点盈亏 d(v)、附加边，判断可行，并给出一组可行流。

原图的边与上下界：

边	lower	upper	cap′ = upper − lower
a → b	1	4	3
b → c	2	4	2
c → a	0	3	3
a → c	1	2	1

各点盈亏 d(v) = Σ入边 lower − Σ出边 lower 与附加边：

点	Σ 入边 lower	Σ 出边 lower	d(v)	附加边
a	0 (c→a)	2 (a→b 1 + a→c 1)	−2	a → tt cap 2
b	1 (a→b)	2 (b→c)	−1	b → tt cap 1
c	3 (b→c 2 + a→c 1)	0 (c→a 0)	+3	ss → c cap 3

正盈亏之和 D = d(c) = 3；负盈亏绝对值之和 = |d(a)| + |d(b)| = 2 + 1 = 3，两者相等（必然如此）。变换后的网络 = 原四条边（容量换成 cap'）+ 三条附加边 $ss\to c (3)$ 、 $a\to tt (2)$ 、 $b\to tt (1)$ 。可行 ⟺ $ss\to tt$ 最大流 = D = 3（三条附加边全满）。

下面在变换后的网络上真跑一遍 $ss \to tt$ 最大流（复用本系列的 maxflowSteps 引擎）。若跑到底总流量 = 3 且三条附加边全部满流，即证明原图存在可行 circulation。

还原可行流 f(e) = lower(e) + g(e):

边	lower	g （变换网络流量）	f = lower + g	区间 [lower, upper]
a → b	1	1	2	[1, 4] ✓
b → c	2	0	2	[2, 4] ✓
c → a	0	3	3	[0, 3] ✓
a → c	1	0	1	[1, 2] ✓

守恒自检： 点 a 入 = f(c→a)=3，出 = f(a→b)+f(a→c)=2+1=3 ✓；点 b 入 = f(a→b)=2，出 = f(b→c)=2 ✓；点 c 入 = f(b→c)=2，出 = f(c→a)=3?——注意 c 还由 $a\to c$ 流入 1，故入 = 2+1 = 3 = 出 3 ✓。每条边都落在自己的 [lower, upper] 内，这就是一组合法的可行 circulation。

6 · 收尾：把约束统一看

上下界只是给每条边的可行域从 [0, cap] 换成 [lower, upper]。它能与本系列别的扩展正交叠加:

上下界 + 费用 = 最小费用可行流 / 最小费用最大流：先按本页求可行流，第二阶段的 $s\to t$ 增广改用「单位费用最短增广路」即可（见最小费用流）。底流部分 $Σ lower(e)\cdot cost(e)$ 是固定成本，叠加在调整成本之上。

更一般的视角：「每条边在区间内取值、每点守恒、目标线性」本质就是一个线性规划 (LP)。下界、上界、守恒都是线性约束；本页的 ss / tt 构造，正是这个 LP 在网络结构下的具体解法。从 LP 与对偶的高度看待最大流 / 最小割 / 这类带界约束，是最自然的统一框架（见 LP 对偶）。