# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3773 |
3 | Radewoosh | 3646 |
4 | ecnerwala | 3624 |
5 | jqdai0815 | 3620 |
5 | Benq | 3620 |
7 | orzdevinwang | 3612 |
8 | Geothermal | 3569 |
8 | cnnfls_csy | 3569 |
10 | gyh20 | 3447 |
# | User | Contrib. |
---|---|---|
1 | awoo | 161 |
2 | maomao90 | 160 |
3 | cry | 158 |
4 | atcoder_official | 156 |
4 | nor | 156 |
6 | -is-this-fft- | 155 |
7 | maroonrk | 154 |
8 | adamant | 153 |
8 | Um_nik | 153 |
10 | djm03178 | 146 |
Name |
---|
Just google ffs
why do you need to be rude? I don't think it is easy to google all these as the topic is really broad and not CP specific, so it would be nice if there is someone experienced that can summarize it as well.
It is
well, not everyone is as good at googling and understanding long wikipedia and fancy math notation as you! :)
To solve a network maximum flow problem you can use the Edmonds-Karp algorithm. It's a bit long, but it's easy to understand.
However, like you said, there are some variation that make Edmonds-Karp not neccessarily the best option.
I know there are a lot of algorithms that solve the max flow problem, but here is a list of the must used algorithms in competitive programming, and some useful topics:
Edmonds-Karp Algorithm (Solves the max-flow in O(VE2))
Dinic's Algorithm (Solves the max-flow in O(V2E))
Bipartite Matching, a special case of the matching problem, which can be solved applying Edmonds-Karp via DFS.
Hopcroft-Karp Algorithm, solves the bipartite matching problem with
overall complexity
Max Flow — Min Cut Theorem
Min Cost Max Flow problem, can be solved using an Edmonds Karp variant, replacing the BFS with a fast Bellman-Ford implementation
The assignment problem (and Min Weight Bipartite Matching), can be solved using min cost max flow
The Hungarian Algorithm, solves the assignment problem with O(n3) complexity
Push-Relabel Algorithm
König's Theorem
Dilworth's Theorem
The last two theorems allows us to solve the Minimum Vertex Cover and Maximum Independent Set problems in bipartite graphs using flow algorithms
One of the most important things about these kind of problems is to find that it is indeed a network flow problem. That's why these topics require a lot of practice.
Personally, I find very hard to understand some algorithms like the Hungarian Method, so it is important to prepare a good library with these implementations. This way we avoid the struggle during contests!
Hope you find this list useful :)
Wow! Thats a great work by you.
But one could just visit this page u know..
Thank you so much. Bookmarked this comment.
I think the topics provided by snacache is enough comprehensive. I'm going to share some links which helped me while learning network flow.
Go through the 4 max flow tutorials from Topcoder tutorials index
Explanation of complexity of Edmonds-Karp (I personally had a tough time understanding the reasoning behind the complexity until I saw this answer. )
Links for understanding Dinic:
Dinic Part 1
Dinic Part 2
Last 6 minutes of this lecture
http://mirror.codeforces.com/blog/entry/52077
For mincost maxflow go through the 3 mincost maxflow tutorials given in the first link for topcoder tutorials
Mincost Maxflow with SPFA (Shortest Path Faster Algorithm) achieves a better average case complexity than mincost maxflow with Bellman Ford. Learn SPFA from here
mind sharing insight like when to use dinic and when to use edmonds? Or is it solely on how dense the graph is?
I actually always use Dinic. Dinic's worst case complexity ( O( V^2 * E )) is better than that of Edmond Karp ( O( V * E^2 ) ). And I haven't heard that Edmond Karp works better in any special graph than Dinic.
I see others have described the algorithms and problems, I'd just add the link to an efficient implementation of Diniz's algorithm here. The page is in Russian (the English version of the page doesn't have Diniz's algorithm yet), Google Translate is your friend. Page also includes efficient implementations of other algorithms in C++.
Atcoder is having a lot of flow problems in ABCs these days. Can someone please share the list of flow problems if one has compiled.