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...
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | ecnerwala | 3649 |
| 2 | Benq | 3581 |
| 3 | orzdevinwang | 3570 |
| 4 | Geothermal | 3569 |
| 4 | cnnfls_csy | 3569 |
| 6 | tourist | 3565 |
| 7 | maroonrk | 3531 |
| 8 | Radewoosh | 3521 |
| 9 | Um_nik | 3482 |
| 10 | jiangly | 3468 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 162 |
| 4 | TheScrasse | 159 |
| 5 | nor | 158 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 151 |
| 8 | SecondThread | 147 |
| 9 | orz | 146 |
| 10 | pajenegod | 145 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 26.04.2024 04:28:31 (i1).
Десктопная версия, переключиться на мобильную.
При поддержке
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. :)
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?
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 ...
thank you, that's a neat trick, I'll keep it in mind in the future...
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
1)
ptr[v]stores the number of the edges adjacent tovalong 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 edgee[id]. And the algorithm requires that if the flow along an edge is x then the flow along its reverse should be - x.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.
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.
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