Geek Answers Handbook

Modification algorithm for maximum flow

I tried to solve the issue of maximum flow problem . I have one source and two sinks. I need to find the maximum flow on this network. This part is the total maximum flow. However, both targets should receive the same amount of flow in this special version of the maximum flow problem.

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

+6
source share
1 answer

Let s be your original vertex and t1 and t2 two shells.

You can use the following algorithm:

  • Use the usual maximum flow with two receivers, for example, connecting t1 and t2 to a superflow through ribs with infinite capacity. Now you have a solution with the maximum value of excess(t1) + excess(t2) , but it may be unbalanced.

  • If excess(t1) == excess(t2) , you're done. Otherwise, wlog let excess(t1) > excess(t2)

  • Start another round of maximum flow with source t1 and flow t2 in the residual network of step 1. Limit the flow coming from t1 to c = floor((excess(t1) - excess(t2)) / 2) , for example, by entering super-source s connected to t1 through an edge with a given capacity c . Now excess(t2) is the maximum flow that you can send to both drains.

  • If you need to restore the flow values ​​for each edge, perform another round of maximum flow to transfer the remaining units of measurement excess(t1) - excess(t2) back to the source code.

Complexity is the maximum flow algorithm.

If you already know how to solve a max stream with a lower bandwidth, you can also perform a binary search for a solution, which will lead to O(log W * f) complexity, where W is the solution value and f is the maximum stream complexity.

+7
source

More articles:


All Articles