gilcu3's blog

Maximum flow
By gilcu3, 12 years ago, In English

Hi everybody, I'm looking for the best max flow algorithm for real competitions, as ACM-ICPC regionals, recently there has been a problem in my regional that needed a very good implementation of Dinic's algorithm or the Hopcroft-Karp matching algorithm, so I'm asking for someone to point out the best performance implementation they have seen...

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

»
12 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Why do you think http://e-maxx.ru/algo/dinic implementation is bad? I got accepted even this problem with that.

Edit: if you didn't even look there, then I have some bad news for you. :)

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

    Thanks, I didn't know about that site, sorry for my poor knowledge, anyway I had that implementation (yet it's the best I have seen), thank you, does anybody knows about a better one?

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

      You can boost your algorithm by matching nodes greedly first, this can be done in O(E) (for each edge -> if its endpoints are unmatched, then match them), thus reducing the number of future augmentations, then run your "heavy fast" algorithm. Note that this greedy matching gives a "maximal" (not maximum) matching of at least n/2 nodes where n is the max matching and is very easy to implement; but doesn't mean that your algorithm will be 2 times faster, it just reduces the overhead introduced by complex algorithms (augmentations, dfs, bfs ...), if you have a good algorithm (and a fast implementation) is very rare that you need such a silly optimization, but it who knows ...

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

        thank you, that's a neat trick, I'll keep it in mind in the future...

        → Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    Could somebody explain me what is the purpose of ptr[MAXN] array ? Unfortunately, I don't know Russian. I swap (; ptr[v]<(int)g[v].size(); ++ptr[v]) { with for (int i=0; i<(int)g[vertex].size(); ++i) { in dfs function and I got the same result. Is it a concidence or using ptr[v] is some kind of optimization ?

    2) Why we need this : e[id^1].flow -= pushed; ? I am refering to the website dreamzor have posted

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      1) ptr[v] stores the number of the edges adjacent to v along which we have already tried to increase flow. It helps to not try to increase flow along one edge multiple times during one iteration of the algorithm's outer loop, so the time complexity of the algorithm is reduced dramatically.

      2) Edge e[id^1] is reverse of edge e[id]. And the algorithm requires that if the flow along an edge is x then the flow along its reverse should be  - x.

      → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Highest label preflow-push algorithm is faster than Dinic's in the worst case, and with heuristics (gap, global relabel) it is faster in the average case (see On Implementing the Push–Relabel Method for the Maximum Flow Problem). Excess scaling preflow-push (see A Fast and Simple Algorithm for the Maximum Flow Problem ) is also very fast especially with heuristics.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it -7 Vote: I do not like it

    Thank you, but this algorithm is more complicated. Could you or someone else answer my previous question, because I can't figure out what this ptr array means.

    → Reply
»
7 years ago, # |
  Vote: I like it -23 Vote: I do not like it

i think that you can use fordfulkerson method with kind of optimization you can send the flow using bit mask so that this algorithm will be done in o(n*n*log(max|v|) ) زit is a good idea but my code has some bugs

→ Reply