algorithm - 最大流量：如何在容量变化最小的情况下强制 f 个单位流动？

Question

假设我有一个图表并在其上运行一个最大流。我得到了一些流量，f。但是，我想在 f1>f 的地方流动 f1 个单位。当然，我需要增加一些边缘容量。我想尽可能少地增加总容量。有没有聪明的算法来实现这一点？

---

如果它有帮助，我关心我的关于二部图的应用程序，其中源（s）到左顶点（L）具有一些有限的整数容量（c_l），左顶点L到右顶点R具有一些具有无限容量的连通性和所有右顶点，R 连接到具有有限整数容量 (c_r) 的汇顶点。在这里，c_l 和 c_r 总和为相同的数字。此外，左侧顶点之间或右侧顶点之间没有连接。

下图中提供了一个示例。蓝色数字是流量，粉红色数字是最大流量中的实际流量。目前，有 5 个单位正在流动，但我想要 9 个单位流动。

标签： algorithmgraphflow

Answer 1

该图是无向的，所有“中间”顶点都有无限容量。这意味着我们可以统一 L 和 R 中由无限容量连接的所有顶点，从而制作一个非常简单的图。

例如，在上图中，等效图将是：

s -8-> Vertex 1+2+4 -4-> t
s -1-> Vertex 3+5   -5-> t

所以我们最终只得到了一堆没有分支的独特路径。我们可以通过简单的“floodfill”或在无限容量边上的 DFS 类型搜索来统一节点。当我们统一节点时，我们将它们的“左”和“右”容量相加。

为了最大化该图中的流量，我们：

• 首先，如果左右路径不相等，则增加较低的路径，直到它们相等。这让我们可以将成本 X 的增加转化为 X 流量的增加。
• 一旦所有节点的左右路径都相等，我们就选择任何路径。然后，我们以 2X 的成本增加路径的两半，使流量增加 X。