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

Автор gilcu3, 12 лет назад, По-английски

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...

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

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

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. :)

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

    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?

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

      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 ...

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

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

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

    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

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

      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.

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

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.

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

    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.

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

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