Just google ffs

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²))

• Dinic's Algorithm (Solves the max-flow in O(V²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³) 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 :)

I think the topics provided by snacache is enough comprehensive. I'm going to share some links which helped me while learning network flow.

1. Go through the 4 max flow tutorials from Topcoder tutorials index

2. Explanation of complexity of Edmonds-Karp (I personally had a tough time understanding the reasoning behind the complexity until I saw this answer. )

3. Links for understanding Dinic:

• Dinic Part 1

• Dinic Part 2

• Last 6 minutes of this lecture

• http://codeforces.me/blog/entry/52077

1. For mincost maxflow go through the 3 mincost maxflow tutorials given in the first link for topcoder tutorials

2. Mincost Maxflow with SPFA (Shortest Path Faster Algorithm) achieves a better average case complexity than mincost maxflow with Bellman Ford. Learn SPFA from here

   • Wiki Article for SPFA
   • wcipeg article for SPFA

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.