# | User | Rating |
---|---|---|

1 | tourist | 3819 |

2 | Benq | 3745 |

3 | ksun48 | 3560 |

4 | Radewoosh | 3511 |

5 | Um_nik | 3489 |

6 | peehs_moorhsum | 3460 |

7 | Petr | 3414 |

8 | Miracle03 | 3410 |

9 | maroonrk | 3400 |

10 | sunset | 3338 |

# | User | Contrib. |
---|---|---|

1 | 1-gon | 207 |

2 | awoo | 182 |

3 | Errichto | 180 |

4 | Um_nik | 179 |

5 | -is-this-fft- | 174 |

5 | maroonrk | 174 |

7 | Radewoosh | 172 |

7 | tourist | 172 |

9 | SecondThread | 170 |

10 | rng_58 | 166 |

↑

↓

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/03/2021 03:54:35 (j1).

Desktop version, switch to mobile version.

Supported by

User lists

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(VE^{2}))Dinic's Algorithm (Solves the max-flow in

O(V^{2}E))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(n^{3}) complexityPush-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://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 withBellman Ford. LearnSPFAfrom heremind 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.