网络流中的可行流问题（Feasible Flow Problem）
问题描述
在网络流中，我们通常有一个源点 \(s\) 和一个汇点 \(t\)，每条边有容量限制，目标是找到从 \(s\) 到 \(t\) 的最大流。
但“可行流问题”更一般：给定一个有向图 \(G = (V, E)\)，每条边 \(e\) 有下界 \(l(e)\) 和上界 \(u(e)\) （即流量必须满足 \(l(e) \leq f(e) \leq u(e)\)），并且每个顶点 \(v\) 可能有净流量需求 \(b(v)\)：
- 若 \(b(v) > 0\)，表示顶点 \(v\) 必须净流出 \(b(v)\) 的流量（即它是“供给点”）。
- 若 \(b(v) < 0\)，表示顶点 \(v\) 必须净流入 \(|b(v)|\) 的流量（即它是“需求点”）。
- 若 \(b(v) = 0\)，则流入流量等于流出流量（流量守恒）。
问题是：是否存在一个流 \(f\)，同时满足边的上下界约束和每个顶点的净流量需求？如果存在，则称该流为可行流。
为什么需要可行流？
可行流问题出现在许多有资源供需约束的场景中，例如：
- 交通流量分配（某些路段有最低通行量要求）。
- 电路设计中的电流平衡。
- 任务分配中每个工人的最低和最高工作量限制。
解题思路：转换为标准最大流问题
可行流问题可以通过构造一个辅助网络 \(G'\)，并转化为一个标准的最大流问题来解决。核心思想是：
- 引入超级源点 \(S\) 和超级汇点 \(T\)。
- 将原图的上下界约束转化为新图中只有上界的容量约束。
- 利用顶点净需求 \(b(v)\) 来构造 \(S\) 到 \(v\) 或 \(v\) 到 \(T\) 的边。
- 在新网络中求最大流，若最大流满流（即所有从 \(S\) 出发的边都饱和），则原问题存在可行流。
详细步骤
第1步：理解流量守恒与净需求
在原图 \(G\) 中，对于顶点 \(v\)，定义：
\[\text{净流出}(v) = \sum_{e \in \text{out}(v)} f(e) - \sum_{e \in \text{in}(v)} f(e) \]
我们需要满足：
\[\text{净流出}(v) = b(v) \quad \forall v \in V \]
第2步：消除下界约束
对于原图每条边 \(e = (u, v)\) 有 \(l(e) \leq f(e) \leq u(e)\)，我们进行变换：
令 \(f'(e) = f(e) - l(e)\)，则新变量 \(f'(e)\) 满足：
\[0 \leq f'(e) \leq u(e) - l(e) \]
但这样修改后，顶点流量守恒会被破坏，因为 \(l(e)\) 的强制流量会影响顶点的净流入流出。我们需要调整顶点的需求。
第3步：计算顶点的“强制流量差额”
定义对于每个顶点 \(v\)：
\[\text{def}(v) = \sum_{e \in \text{in}(v)} l(e) - \sum_{e \in \text{out}(v)} l(e) \]
即，仅考虑下界时，\(v\) 的净流入（如果为正）或净流出（如果为负）。
那么，在考虑实际需求 \(b(v)\) 后，顶点 \(v\) 在新图中需要满足的净流出应为：
\[b'(v) = b(v) - \text{def}(v) \]
解释：下界强制带来的流量已经贡献了一部分净流出，所以需求要减去这部分。
第4步：构造辅助网络 \(G'\)
- 保留原图所有边，但将容量改为 \(u(e) - l(e)\)（即 \(f'(e)\) 的上界）。
- 添加超级源点 \(S\) 和超级汇点 \(T\)。
- 对每个顶点 \(v\)：
- 如果 \(b'(v) > 0\)，表示它还需要净流出 \(b'(v)\)，所以从 \(S\) 向 \(v\) 连边，容量为 \(b'(v)\)（让 \(S\) 给它“供应”流量，它再流出去）。
- 如果 \(b'(v) < 0\)，表示它需要净流入 \(|b'(v)|\)，所以从 \(v\) 向 \(T\) 连边，容量为 \(-b'(v)\)（让它把多余流量排给 \(T\)）。
- 在原图中，如果某条边 \(e\) 的下界 \(l(e) > 0\)，我们已经通过 \(\text{def}(v)\) 调整了需求，因此不需要在 \(G'\) 中显式表示下界。
第5步：在 \(G'\) 中求最大流
在 \(G'\) 中，从 \(S\) 到 \(T\) 跑一次最大流算法（如 Edmonds-Karp 或 Dinic）。
设最大流值为 \(F\)。令：
\[D = \sum_{b'(v) > 0} b'(v) \]
即所有正需求的总和。
如果 \(F = D\)，说明所有从 \(S\) 出发的边都满流，意味着所有顶点的调整后需求 \(b'(v)\) 都被满足，则原问题存在可行流。
如果 \(F < D\)，则不存在可行流。
第6步：还原原图的可行流
如果存在可行流，对于原图每条边 \(e\)：
\[f(e) = f'(e) + l(e) \]
其中 \(f'(e)\) 是 \(G'\) 中该边的流量值（来自最大流结果）。
举例说明
假设一个简单有向图：顶点 \(\{1, 2\}\)，边 \((1, 2)\) 有下界 \(2\)、上界 \(5\)。
需求：\(b(1) = 2\)（顶点1需净流出2），\(b(2) = -2\)（顶点2需净流入2）。
步骤：
- 计算 \(\text{def}(1) = -2\)（流出下界2，所以净流出 -2？注意：def(v) = 流入下界 - 流出下界）：
- 顶点1：流入下界和=0，流出下界和=2 ⇒ def(1) = -2
- 顶点2：流入下界和=2，流出下界和=0 ⇒ def(2) = 2
- 计算 \(b'(v)\)：
- \(b'(1) = b(1) - def(1) = 2 - (-2) = 4\)
- \(b'(2) = b(2) - def(2) = (-2) - 2 = -4\)
- 构造 \(G'\)：
- 边 (1,2)：容量 = \(5 - 2 = 3\)
- 从 S→1 连容量 4 的边
- 从 2→T 连容量 4 的边
- 在 \(G'\) 中求最大流：S→1→2→T 可流 3 单位，但 S→1 容量为 4，未满流 ⇒ 最大流 F=3，而 D=4，F < D，故无可行流。
检查原因：边 (1,2) 下界 2 强制从 1 流向 2 至少 2，但需求 b(1)=2 要求 1 净流出正好 2，所以边 (1,2) 流量只能是 2（因为 2 没有其他边），但这样顶点 2 得到流入 2，需求 b(2)=-2 满足（净流入 2），顶点 1 流出 2 也满足。等一下，我们计算一下：
如果 \(f(1,2) = 2\)：- 顶点1：净流出 = 2 ⇒ 满足 b(1)=2
- 顶点2：净流入 = 2 ⇒ 满足 b(2)=-2
看起来是可行的？哪里出错了？
错误在于 def(1) 计算：def(1) = 流入下界和 - 流出下界和 = 0 - 2 = -2。
b'(1) = 2 - (-2) = 4，这意味着在去掉下界后，顶点1需要额外净流出 4（因为下界已经贡献了净流出 -2？不对，需要仔细理解）。
实际上，下界 l=2 意味着边 (1,2) 至少有 2 的流量从 1 到 2。那么顶点1因这条边至少流出 2，顶点2至少流入 2。需求 b(1)=2 要求顶点1净流出 2，下界已经满足这个需求；需求 b(2)=-2 要求顶点2净流入 2，下界也满足。所以应该存在可行流，只需取 f(1,2)=2 即可。
为什么我们的转换说不可行？因为我们在转换中把下界减掉后，顶点1需要额外流出 4，但边 (1,2) 在新图中容量只有 3，无法提供 4 的流量，所以 G' 中无满流。但这里其实我们误用了需求调整公式。正确的理解是：下界已经满足了部分需求，所以需求应减去下界贡献。
检查顶点1：原来需要净流出 2，下界贡献了净流出 2（因为只有一条出边且下界为 2），所以调整后需求 b'(1) 应为 0。类似地，顶点2：原来需要净流入 2，下界贡献了净流入 2，所以 b'(2)=0。这样 G' 中不需要 S 和 T 的边，直接验证即可。
所以修正：计算 def(v) 时，应理解为“下界带来的净流入”，而 b(v) 是“希望的总净流出”，所以调整后需求为：
\[ b'(v) = b(v) - \left( \sum_{\text{in}(v)} l(e) - \sum_{\text{out}(v)} l(e) \right) = b(v) - \text{def}(v) \]
本例中 def(1) = 0 - 2 = -2（下界带来的净流入是 -2，即净流出 2），b(1)=2 ⇒ b'(1) = 2 - (-2) = 4（确实需要额外流出 4？矛盾）。
其实正确公式应为：
\[ \text{新需求} = b(v) - \left( \sum_{\text{out}(v)} l(e) - \sum_{\text{in}(v)} l(e) \right) \]
这样 def(1) = 2 - 0 = 2（下界带来的净流出为 2），b'(1) = 2 - 2 = 0。def(2) = 0 - 2 = -2（下界带来的净流出为 -2，即净流入 2），b'(2) = -2 - (-2) = 0。
所以 G' 中 b'(v) 全为 0，不需要 S 和 T 的边，直接存在可行流。
因此，我最初写的 def(v) 定义符号是反的，导致例子计算错误。实际算法中，常用：
\[ \text{net-demand}(v) = b(v) + \sum_{\text{in}(v)} l(e) - \sum_{\text{out}(v)} l(e) \]
这样若 net-demand(v) > 0，则从 S 向 v 连边；若 < 0，则从 v 向 T 连边（容量为 -net-demand(v)）。
在本例中，net-demand(1) = 2 + 0 - 2 = 0，net-demand(2) = -2 + 2 - 0 = 0，因此无需额外边，可行流存在。
算法总结
- 计算每个顶点 \(v\) 的 净需求调整值：
\[ d(v) = b(v) + \sum_{e \in \text{in}(v)} l(e) - \sum_{e \in \text{out}(v)} l(e) \]
- 构建辅助网络 \(G'\)：
- 原边 \(e = (u,v)\) 容量改为 \(u(e) - l(e)\)。
- 添加超级源 \(S\) 和超级汇 \(T\)。
- 若 \(d(v) > 0\)，加边 \(S \to v\) 容量 \(d(v)\)。
- 若 \(d(v) < 0\)，加边 \(v \to T\) 容量 \(-d(v)\)。
- 在 \(G'\) 中求 \(S\) 到 \(T\) 的最大流 \(F\)。
- 若 \(F = \sum_{d(v) > 0} d(v)\)（即所有从 \(S\) 出发的边满流），则原问题有可行流。
- 还原原图流量：\(f(e) = f_{G'}(e) + l(e)\)。
通过以上转换，我们将一个带下界和顶点供需约束的可行流问题，转化为一个标准的最大流问题，从而利用经典算法求解。