Rare
 0/5

Maximum Flow

Author: Benjamin Qi

Introduces maximum flow as well as flow with lower bounds.

StatusSourceProblem NameDifficultyTagsSolution
CSESEasy
Show Tags

Max Flow

View Solution

Resources

Flows

StatusSourceProblem NameDifficultyTagsSolution
CSESEasy
Show Tags

Max Flow

View Solution

Bipartite Matching

StatusSourceProblem NameDifficultyTagsSolution
CSESEasy
Show Tags

Max Flow

View Solution

Dinic's Algorithm

StatusSourceProblem NameDifficultyTagsSolution
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:

Give Us Feedback on Maximum Flow!