Checking lower constraints in networks with cycles

Правка en6, от jvmusin, 2019-08-03 22:25:11

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): https://e-maxx.ru/algo/flow_with_limits). 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 on the networks with cycles?

Теги max-flow, e-maxx

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en8 Английский jvmusin 2019-08-03 22:26:04 4 Tiny change: 'raints in the networks ' -> 'raints in networks '
en7 Английский jvmusin 2019-08-03 22:25:45 2 Tiny change: 'ontraints on the netw' -> 'ontraints in the netw'
en6 Английский jvmusin 2019-08-03 22:25:11 26
en5 Английский jvmusin 2019-08-03 22:16:29 0 (published)
en4 Английский jvmusin 2019-08-03 22:14:58 12
en3 Английский jvmusin 2019-08-03 22:12:03 224 Tiny change: 'ng" width=80% height=80% class="' -> 'ng" width=40% height=40% class="'
en2 Английский jvmusin 2019-08-03 22:02:09 54
en1 Английский jvmusin 2019-08-03 22:01:02 1389 Initial revision (saved to drafts)