Musin's blog

By Musin, history, 14 months ago, In English

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 in networks with cycles?

Read more »

 
 
 
 
  • Vote: I like it
  • +8
  • Vote: I do not like it

By Musin, history, 14 months ago, translation, In English

After submitting a solution and watching submissions page, it doesn't update (Testing on test x is static). When i press F5 it updates, but still being static, so i have to press F5 to update it again.

Chrome says net::ERR_CERT_DATE_INVALID.

Does anyone have the same problem?

Read more »

 
 
 
 
  • Vote: I like it
  • +128
  • Vote: I do not like it