修改最大流算法 [英] Modification to Maximum Flow Algorithm

问题描述

我试图解决有关最大流问题的问题。我有一个源和两个水槽。我需要找到在这个网络中的最大流量。这部分是通用最大流。但是，这两个指标都得到了最大流问题的这一特殊版本的流量相同。

I've tried to solve a question about the maximum-flow problem. I have one source and two sinks. I need to find a maximum flow in this network. This part is general max-flow. However, both targets have to get same amount of flow in this special version of the max-flow problem.

是否有任何人谁可以帮助我该怎么做才能做到这一点？

Is there anyone who can help me what should I do to do that?

推荐答案

让取值是你的源点和 T1 和 T2 的两个水槽。

Let s be your source vertex and t1 and t2 the two sinks.

您可以使用下面的算法：

You can use the following algorithm:

1. 通过连接使用常规最大流和两个洗手池，例如 T1 和 T2 到通过与无限容量的边缘超水槽。现在，您有最大的过量（T1）+过量（T2）的解决方案，但它可能会不平衡。

1. Use regular max-flow with two sinks, for example by connecting t1 and t2 to a super-sink via edges with infinite capacities. You now have the solution with maximum excess(t1) + excess(t2), but it might be imbalanced.

如果过量（T1）==过量（T2），你做。否则，w.l.o.g.让过量（T1）＆GT;过量（T2）

If excess(t1) == excess(t2), you are done. Otherwise, w.l.o.g. let excess(t1) > excess(t2)

运行另一轮最大流与源 T1 和汇 T2 中的剩余网络第1步：限制流量传出从 T1 到 C =楼（（过量（T1） - 过量（T2））/ 2），例如通过边缘与给定容量引入超源取值连接到 T1 C 。现在，过剩（T2）是可以发送到两个接收器的最大流量。

Run another round of max-flow with source t1 and sink t2 in the residual network of step 1. Restrict the flow outgoing from t1 to c = floor((excess(t1) - excess(t2)) / 2), for example by introducing a super-source S connected to t1 via an edge with the given capacity c. Now, excess(t2) is the maximum flow you can send to both sinks.

如果您需要重建的流量值每条边，做了又一轮最大流的输送过量（T1） - 过量（T2）流回源的剩余单位。

If you need to reconstruct the flow values for each edge, do another round of max-flow to transport the excess(t1) - excess(t2) leftover units of flow back to the source.

的复杂性在于，你的最大流算法。

The complexity is that of your max-flow algorithm.

如果你已经知道如何解决最大流与下限的能力，也可以二进制搜索的解决方案，从而在复杂 O（日志W * F）其中，是W 是解决方案的价值和 F 是最大流的复杂性。

If you already know how to solve max-flow with lower-bound capacities, you can also binary search the solution, resulting in complexity O(log W * f) where W is the solution value and f is the max-flow complexity.

这篇关于修改最大流算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！