Checking lower constraints in networks with cycles

Revision en8, by Musin, 2019-08-03 22:26:04

Hello, Codeforces!

Recently I was solving max-flow problems, here is one of the problems I can't solve.

You're given a network with min and max constraints on the edges. For simplicity suppose all the edges have capacity=1. For example, you have the following network:

We want to put a lower constraint on the edge C->D so that it's min=1 and check whether there exists a flow from S to T which uses the edge C->D. Note that it's unable in the given example. To find max flow on this network, we should change it slightly to remove lower constraints from the edges (algorithm is here (on russian): After these changes we will get the following network (I removed edge C->D with capacity 0 from the image):

Now run any max-flow algorithm and it will find the next flow (yellow edges are used edges):

As you can see, the flow is found and it means that we can use these edges in the original network and we will get the flow from S to T with edge C->D. Restore the original network now:

But, as you can see, this is not the flow from S to T.

So, my question is: How to check lower contraints in networks with cycles?

Tags max-flow, e-maxx


  Rev. Lang. By When Δ Comment
en8 English Musin 2019-08-03 22:26:04 4 Tiny change: 'raints in the networks ' -> 'raints in networks '
en7 English Musin 2019-08-03 22:25:45 2 Tiny change: 'ontraints on the netw' -> 'ontraints in the netw'
en6 English Musin 2019-08-03 22:25:11 26
en5 English Musin 2019-08-03 22:16:29 0 (published)
en4 English Musin 2019-08-03 22:14:58 12
en3 English Musin 2019-08-03 22:12:03 224 Tiny change: 'ng" width=80% height=80% class="' -> 'ng" width=40% height=40% class="'
en2 English Musin 2019-08-03 22:02:09 54
en1 English Musin 2019-08-03 22:01:02 1389 Initial revision (saved to drafts)