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?