其中，$ b(v) $ 是顶点 $ v $ 的净需求（supply/demand）。
*   如果 $ b(v) > 0 $，则 $ v $ 是一个**供应点**（supply node），它必须“产生” $ b(v) $ 单位的净流出。
*   如果 $ b(v) < 0 $，则 $ v $ 是一个**需求点**（demand node），它必须“吸收” $ |b(v)| $ 单位的净流入。
*   如果 $ b(v) = 0 $，则 $ v $ 是一个**转运点**（transshipment node），流入等于流出。

    这个值表示，如果所有边都只流过其下界流量 $ l(e) $，那么顶点 $ v $ 的“预置”净流入是多少（正值表示净流入，负值表示净流出）。
*   根据 $ M(v) $ 和 $ b(v) $ 的关系，添加从超级源点 $ s $ 或到超级汇点 $ t $ 的边：
    *   计算顶点的“调整需求” $ D(v) = b(v) - M(v) $。
    *   如果 $ D(v) > 0 $，意味着顶点 $ v $ 在满足所有边下界后，还需要额外获得 $ D(v) $ 单位的净流入，才能满足其净需求 $ b(v) $。那么我们在 $ G' $ 中添加一条从**超级源点 $ s $** 到 $ v $ 的边，容量为 $ D(v) $。这表示超级源点可以“提供”这部分不足的流量。
    *   如果 $ D(v) < 0 $，意味着顶点 $ v $ 在满足所有边下界后，反而有 $ |D(v)| $ 单位的净流出盈余，需要被“消耗”掉。那么我们在 $ G' $ 中添加一条从 $ v $ 到**超级汇点 $ t $** 的边，容量为 $ -D(v) $。这表示超级汇点可以“吸收”这部分多余的流量。
    *   如果 $ D(v) = 0 $，则无需添加与 $ s, t $ 相连的边。

*   可以验证，这样构造的 $ f_{original}(e) $ 满足 $ l(e) \le f_{original}(e) \le c(e) $，并且每个顶点 $ v $ 的流量守恒值为 $ b(v) $。

网络流中的可行流问题（Feasible Flow Problem） 问题描述 给定一个有向图 \( G = (V, E) \)，其中每条边 \( e = (u, v) \) 有一个非负的容量下界 \( l(e) \) 和一个容量上界 \( c(e) \) （满足 \( 0 \le l(e) \le c(e) \)）。同时，为每个顶点 \( v \) 指定一个“净需求” \( b(v) \)。 可行流问题要求我们判断是否存在一个流函数 \( f: E \rightarrow R^+ \)，满足以下三个条件： 容量约束 ：对于每条边 \( e \in E \)，有 \( l(e) \le f(e) \le c(e) \)。 流量守恒 ：对于每个顶点 \( v \in V \)，有： \[ \sum_ {(u, v) \in E} f(u, v) - \sum_ {(v, w) \in E} f(v, w) = b(v) \] 其中，\( b(v) \) 是顶点 \( v \) 的净需求（supply/demand）。 如果 \( b(v) > 0 \)，则 \( v \) 是一个 供应点 （supply node），它必须“产生” \( b(v) \) 单位的净流出。 如果 \( b(v) < 0 \)，则 \( v \) 是一个 需求点 （demand node），它必须“吸收” \( |b(v)| \) 单位的净流入。 如果 \( b(v) = 0 \)，则 \( v \) 是一个 转运点 （transshipment node），流入等于流出。 目标 ：判断是否存在满足上述所有条件的可行流。如果存在，通常还需要构造出一个具体的流方案。 应用场景 ：这个模型非常通用，可用于资源分配、生产计划、交通流量平衡、电路电流设计等场景，其中每个节点有确定的供给或需求，边有输送能力的上下限。 解题过程（转化为最大流问题） 可行流问题可以通过构造一个辅助的 最大流问题 来求解。核心思想是：将带有下界的流量约束，转化为一个只有容量上界的标准网络流问题，并通过引入超级源点和超级汇点来满足所有节点的净需求约束。 步骤 1：构造辅助网络 \( G' \) 我们基于原图 \( G \) 构造一个新的流网络 \( G' = (V', E') \)。 顶点集 ：\( V' = V \cup \{s, t\} \)，其中 \( s \) 是新的 超级源点 ，\( t \) 是新的 超级汇点 。 边集与容量 ： 对于原图 \( G \) 中的每条边 \( e = (u, v) \)，其在 \( G' \) 中对应一条从 \( u \) 到 \( v \) 的边，容量设为 \( c(e) - l(e) \)。这意味着在 \( G' \) 中，我们只考虑可以“自由”调节的那部分流量（超出强制下界 \( l(e) \) 的部分）。 对于每个顶点 \( v \in V \)，计算其 净下界流量 \( M(v) \)： \[ M(v) = \sum_ {\text{入边 } e} l(e) - \sum_ {\text{出边 } e} l(e) \] 这个值表示，如果所有边都只流过其下界流量 \( l(e) \)，那么顶点 \( v \) 的“预置”净流入是多少（正值表示净流入，负值表示净流出）。 根据 \( M(v) \) 和 \( b(v) \) 的关系，添加从超级源点 \( s \) 或到超级汇点 \( t \) 的边： 计算顶点的“调整需求” \( D(v) = b(v) - M(v) \)。 如果 \( D(v) > 0 \)，意味着顶点 \( v \) 在满足所有边下界后，还需要额外获得 \( D(v) \) 单位的净流入，才能满足其净需求 \( b(v) \)。那么我们在 \( G' \) 中添加一条从 超级源点 \( s \) 到 \( v \) 的边，容量为 \( D(v) \)。这表示超级源点可以“提供”这部分不足的流量。 如果 \( D(v) < 0 \)，意味着顶点 \( v \) 在满足所有边下界后，反而有 \( |D(v)| \) 单位的净流出盈余，需要被“消耗”掉。那么我们在 \( G' \) 中添加一条从 \( v \) 到 超级汇点 \( t \) 的边，容量为 \( -D(v) \)。这表示超级汇点可以“吸收”这部分多余的流量。 如果 \( D(v) = 0 \)，则无需添加与 \( s, t \) 相连的边。 步骤 2：在辅助网络 \( G' \) 上求最大流 在构造好的网络 \( G' \) 上，从超级源点 \( s \) 到超级汇点 \( t \) 运行一个标准的最大流算法（如Edmonds-Karp, Dinic等），求出最大流的值 \( F \)。 步骤 3：判断可行性与构造解 可行性判定 ：设 \( D_ {total} = \sum_ {v: D(v)>0} D(v) \)（即所有从 \( s \) 出发的边的容量之和）。 当且仅当 在 \( G' \) 中求得的 最大流 \( F \) 等于 \( D_ {total} \) 时，原问题存在可行流。 原理 ：\( D_ {total} \) 代表了整个网络需要从超级源点“补充”的总流量。如果最大流 \( F \) 能将其全部送达超级汇点，说明我们能够找到一种流量分配方式，在满足所有边上下界的同时，精确地“调和”了每个顶点的净需求。否则，说明约束条件无法被同时满足。 构造原问题的可行流 ： 如果判定为可行，我们可以构造出原图 \( G \) 中的一个可行流 \( f_ {original} \)。 对于原图 \( G \) 中的每条边 \( e = (u, v) \)，其在辅助网络 \( G' \) 中对应边的流值为 \( f'(u, v) \)（即“自由”部分流过的流量）。那么原图中的流值为： \[ f_ {original}(e) = l(e) + f'(u, v) \] 可以验证，这样构造的 \( f_ {original}(e) \) 满足 \( l(e) \le f_ {original}(e) \le c(e) \)，并且每个顶点 \( v \) 的流量守恒值为 \( b(v) \)。 举例说明 假设有一个简单有向图，顶点为 {A, B}，边为 (A->B)。 已知：\( l(A, B) = 2, c(A, B) = 5, b(A)=3, b(B)=-3 \)。（A点需净流出3，B点需净流入3）。 构造 \( G' \) ： 边 (A, B) 在 \( G' \) 中容量为 \( c - l = 5-2 = 3 \)。 计算 \( M(A) = 0 - 2 = -2 \)（出边下界和为2，入边下界和为0）， \( D(A) = b(A)-M(A)=3-(-2)=5>0 \)，因此添加边 \( s \to A \)，容量为5。 计算 \( M(B) = 2 - 0 = 2 \)， \( D(B) = b(B)-M(B) = (-3) - 2 = -5 < 0 \)，因此添加边 \( B \to t \)，容量为5。 \( D_ {total} = 5 \)。 在 \( G' \) 上求最大流 ： 路径 \( s \to A \to B \to t \) 上可以流过3的流量（受限于边 A->B 的容量3）。但 \( D_ {total}=5 \)，最大流 \( F=3 < 5 \)。 结论 ：不存在可行流。因为边 (A, B) 即使取到最大容量5，也只能从A输送5单位流量到B。但根据下界和需求，A必须至少净流出3，B必须至少净流入3，这需要边 (A,B) 的流量至少为3（满足需求），且不超过5（满足容量）。然而，计算 \( M(A)=-2, D(A)=5 \) 意味着，为了满足A的净流出3，在流过下界2之后，还需要通过边 (A,B) 额外再流出5单位，这超过了该边的剩余容量3，因此不可行。 如果我们修改条件，设 \( b(A)=2, b(B)=-2 \)，其他不变。 则 \( D(A) = 2 - (-2) = 4 \)， \( D(B) = (-2) - 2 = -4 \)， \( D_ {total}=4 \)。 在 \( G' \) 中，路径 \( s \to A \to B \to t \) 上可以流过3的流量（仍受限于边 A->B 容量3）。但此时 \( D_ {total}=4 \)，最大流 \( F=3 < 4 \)，仍然不可行？这里似乎有矛盾，因为直观上让 \( f(A,B)=2 \) 似乎就能满足（A净流出2，B净流入2）。让我们重新计算： 当 \( f(A,B)=2 \) 时，满足下界和容量。对于A点：流出2，流入0，净流出2，满足 \( b(A)=2 \)。 对于B点：流入2，流出0，净流入2，满足 \( b(B)=-2 \) (因为-2表示需要净流入2)。等等，这里似乎符号约定容易混淆。通常我们定义 \( b(v) \) 为正表示净流出（供给），为负表示净流入（需求），或者反过来。在标准可行流定义中，常见的是 \( \sum f(in) - \sum f(out) = b(v) \)。如果 \( b(v)>0 \)，表示净流入（像一个汇点）， \( b(v)<0 \) 表示净流出（像一个源点）。让我们明确采用此定义： b(v) 表示顶点v的净流入量 。 重新审视第一个例子：\( b(A)=3 \) 表示A需要净流入3， \( b(B)=-3 \) 表示B需要净流出3。这要求从B到A有3的净流量，但边是A到B，方向反了，所以不可行，结果正确。 在第二个修改的例子中：\( b(A)=2 \) 表示A需要净流入2， \( b(B)=-2 \) 表示B需要净流出2。边是A到B。如果流量 \( f(A,B)=0 \)， 对A：流入0-流出0=0， 不等于2。如果 \( f(A,B)=2 \)， 对A：流入0-流出2=-2，不等于2。如果 \( f(A,B)=x \)， 对A：净流入为 \( 0 - x = -x \)， 要等于2， 则 \( x=-2 \)，不可能。所以确实也不可行。计算验证： \( M(A) = 0 - 2 = -2 \)， \( D(A) = b(A)-M(A) = 2 - (-2) = 4 \)。 \( M(B) = 2 - 0 = 2 \)， \( D(B) = b(B)-M(B) = (-2) - 2 = -4 \)。 在 \( G' \) 中，边 (A,B) 容量为3。从s到A有容量4，从B到t有容量4。最大流为 min(4, 3, 4) = 3， 不等于 \( D_ {total}=4 \)，判定不可行。结果一致。 总结 ：网络流中的可行流问题通过巧妙的图变换，将带下界和节点供需约束的复杂问题，转化为一个标准的最大流问题进行求解。其核心步骤是：构造辅助网络、在辅助网络上求最大流、通过比较最大流值与总需求来判断可行性，并在可行时通过简单的反向计算得到原问题的解。这是一个将“存在性”问题转化为“优化”问题的经典范例。