xuanquang1999's blog

By xuanquang1999, history, 7 years ago, In English

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.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
6 years ago, # |
  Vote: I like it +5 Vote: I do not like it

I had the same RE as you. The problem is while (scanf("%d%d", &n, &m) != EOF). To get AC, you should write while (scanf("%d%d", &n, &m) == 2). Why? Maybe because they have wrong input files.

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      click
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Sure, Edmons-Karp should be enough.