假设我有一个图表并在其上运行最大流。我得到了一些流量，f。但是，我想在 f1>f 的地方流动 f1 个单位。当然，我需要着手增加一些边缘容量。我想尽可能小地增加容量。是否有聪明的算法来实现这一目标？
如果有帮助，我关心我的二分图的应用，其中源 (s) 到左顶点 (L) 具有一些有限的整数容量 (c_l)，左顶点 L 到右顶点 R 具有无限连通性容量和所有正确的顶点，R 连接到具有有限整数容量 (c_r) 的汇点顶点。在这里，c_l 和 c_r 总和为相同的数字。此外，左顶点或右顶点之间没有连接。
下图中提供了一个示例。蓝色数字是流量，粉红色数字是最大流量中的实际流量。目前，有 5 个单位在流动，但我想要 9 个单位在流动。
最佳答案
一般来说，通过将现有弧的成本设置为零并添加新的、无限容量的弧使其成本一加倍，将流实例转变为最小成本流实例。
对于这些特定情况，您要做的最好的事情就是反复找到有限容量的不饱和弧，并沿着包含它的任何路径插入流量。一旦一切都饱和了，就使用任何路径。
这似乎有点太容易成为您想要的，所以我会提到可以制定更复杂的目标并使用线性规划技术来解决它们。
关于algorithm - 最大流量 : how to force f units to flow, 容量变化最小？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/64310839/