Rare
 0/5

Maximum Flow

Author: Benjamin Qi

Introduces maximum flow as well as flow with lower bounds.

StatusSourceProblem NameDifficultyTagsSolutionURL
CSESEasy
Show Tags

Max Flow

View Solution

Resources

Flows

StatusSourceProblem NameDifficultyTagsSolutionURL
CSESEasy
Show Tags

Max Flow

View Solution

Bipartite Matching

StatusSourceProblem NameDifficultyTagsSolutionURL
CSESEasy
Show Tags

Max Flow

View Solution

Dinic's Algorithm

StatusSourceProblem NameDifficultyTagsSolutionURL
SPOJEasyView Solution
YSEasyView Solution

Hopcroft-Karp Bipartite Matching?

Optional: Faster Flow

There exist faster flow algorithms such as Push-Relabel. Also see the following blog post:

However, the standard implementation of Dinic's is (almost) always fast enough on reasonable problems.

Implementation

Resources
Benq

Breaking Flows

When the constraints are too high ...

Module Progress:

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

Give Us Feedback on Maximum Flow!

Leave suggestions for us by making a post on the USACO Forum! Ex: Unclear sections, mislabeled problems, etc.