graph - 给定边缘约束的最大流量

Question

嘿，所以我有一个图，例如 3 条边进入一个节点，3 条边出来，但是如果一个特定的输入边有容量，我只需要激活输出边。例如，如果我们有：

A -> N

B -> N

C -> N

N -> N'

N' -> A'

N' -> B'

N' -> C'

如果 A 有流量，我只想流过 A'，如果 B 有流量等，我只想流过 B'。

基本上它是边缘 A、B、C 的容量限制器，我最初无法限制它们的容量。

假设这种情况发生多次，我如何将此约束添加到最大流量并解决给定图的最大流量图问题？

编辑：我最终也不能限制它们的容量，因为稍后会在图中使用 A'、B' 和 C'，所以我不能将 N 和 N' 移动到最后并在以后强制组合容量减少。

Answer 1

如果目标是将离开 a、b 和 c 的组合流限制为 n->n' 的容量，则只需将 n 个节点移动到图的另一侧。换句话说，您可以简单地通过从 a、b 和 c 获取流量并将其直接（或通过它们的素数对）引导至 n，然后从 n 直接（或再次通过 n'）引导至您的接收器来模拟您的问题。

编辑：您也可以将 n 放在 a/b/c 之前以获得相同的效果。

编辑 2：如果您谈论的是 ford fulkerson 的实现，理论上您可以在列出扩充路径时过滤掉您不想要的路径。例如，当您的程序识别出可能的增广路径时，如果它使流 a->n 不等于 n'->a' 等，则不要沿着它增广。