I'm trying to solve B — Safety Grade from SEERC 2011. My solution is to iterate over all the pair of vertices in the graph (let's call the pair (s, t)), calculate the maximum flow (using Edmond-Karp algorithm) from s to t, and the answer is the minimum value among these max flow value. Also, notice that the answer can't exceed the minimum of each vertex's degree (which won't exceed ), so each maximum flow calculation will be done in less than BFS. So, the overall complexity of the algorithm is O(n * m2).
I don't know why my solution got Runtime Error (that's the last verdict I would expect to get in this problem). I ran stress-testing for half an hour, but couldn't find any wrong test case. I need help finding what's wrong with my implementation. Thanks in advance.
Did you manage to solve the problem ? I am also trying to solve the same problem but got no idea how to do it. If you solved the problem, can you please help me by posting your source code or giving a brief explanation of your approach. Thanks.
I had the same RE as you. The problem is
while (scanf("%d%d", &n, &m) != EOF)
. To get AC, you should writewhile (scanf("%d%d", &n, &m) == 2)
. Why? Maybe because they have wrong input files.Can you please share your source code? I did not find any on the internet. Doing the modifications you suggested in the source code by the author of this blog still yields a WA on live archive oj.
Thanks a lot. :) BTW, can this problem be solved by using edmonds-karp as well, or do we need dinic for it? Because the blog author's solution implements edmonds-karp. I tried using the same idea but got WAs or REs.
Sure, Edmons-Karp should be enough.