Блог пользователя game_changer007

Автор game_changer007, история, 8 лет назад, По-английски

Hi,I am trying to solve this problem on Spoj.

I have implemented simple Dinic's algorithm only,but am getting TLE.Here is the solution link solution .Am I doing anything wrong?

Please help!!

Edit:Got AC!!

  • Проголосовать: нравится
  • +2
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

In your dfs function you are unnecessarily iterating over the used edges. You only need to start from scratch whenever you recompute the bfs function(), and not everytime.

In short

1)Make a ptr[] array (size >= number of vertices)

2)change line 75 to for(;ptr[u]<g[u].size();++ptr[u]) //ptr[u] stores your position in g[u]

3)Do a memset(ptr,0,sizeof ptr) after your bfs function returns true

http://e-maxx.ru/algo/dinic

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    AC :) Thanks... Learned something new!!

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Welcome :)

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Hi!! Another question..Is Dinic's algorithm the same as Hopcroft-Karp algorithm??

        Do we need to make any changes in Dinic's to make it Hopcroft-Karp?If yes,then how and in which part?

        • »
          »
          »
          »
          »
          8 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится -8 Проголосовать: не нравится

          I wasn't right.

        • »
          »
          »
          »
          »
          8 лет назад, # ^ |
            Проголосовать: нравится +9 Проголосовать: не нравится

          Actually, Hopcroft-Karp is an algorithm to find the maximum matching in a bipartite graph (and it has the same time complexity as Dinic's algorithm on bipartite graphs, but it's much faster in practice). You can always implement bipartite matching with Dinic's, but Hopcroft-Karp is easier to code in my opinion.

          • »
            »
            »
            »
            »
            »
            8 лет назад, # ^ |
            Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

            Hi!! As you said that Dinic's has the same complexity as Hopcroft-Karp for maximum matching... But am getting TLE for this problem on applying Dinic's algorithm.

            My solution is this.Am i missing anything??? I read that HK is accepted in this problem..So should i conclude that HK is faster than Dinic's in general?

            • »
              »
              »
              »
              »
              »
              »
              8 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              Dinic's has the same complexity as Hopcroft-Karp in bipartite graphs. I guess you should do constant optimizations (because there are people who got AC with Dinic's) or change stuff such as the order of some fors (n -> 1 instead of 1 -> n). If all else fails, implement Push-Relabel (Which is a guaranteed AC with heuristics, but much painful to code).

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    can you explain the statement fl=mini(fl,cap[u][to]-flow[u][to]); in the code.You are passing the bottleneck of one of the edge into all the children

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Another way of changing it is just adding something like d[u] = 1000000000ll before return 0 in the dfs.

Here is an accepted solution of your code: http://ideone.com/LBl7V9