Rare
 0/5

Maximum Flow

Authors: Benjamin Qi, Mihnea Brebenel

Introduces maximum flow as well as flow with lower bounds.

StatusSourceProblem NameDifficultyTags
CSESEasy
Show TagsMax Flow

Solution

Edmonds-Karp Algorithm

The Edmonds-Karp algorithm uses a greedy approach to solve the maximum flow problem.

The download speed (the flow) can be improved as long as we can find a non-negative capacity path from the source (the server) and the sink (Kotivalo's computer). After that, we subtract the minimum capacity on the found path from the edge capacities.

C++

#include <bits/stdc++.h>
using namespace std;
long long max_flow(vector<vector<long long>> g, int n, int source, int sink) {
long long flow = 0;
vector<int> parent(n, -1);
// Find a way from the source to sink on a path with non-negative capacities
auto reachable = [&]() -> bool {
queue<int> q;

Push-Relabel Algorithm

The Push-Relabel Algorithm is an alternative solution to finding the maximum flow.

To find the maximum flow, we'll handle a preflow. The only difference between this and a normal flow is that the incoming flow can exceed the outgoing flow.

Let's define the excess flow of node u as inuoutuin_u - out_u, where inin is the incoming flow and outout is the outgoing flow.

The algorithm starts with an initial preflow where the source has an excess flow. At every stage, it picks a node with the excess flow and pushes the excess to its neighbors, if the capacity supports it. To push excess flow from node uu to node vv, we define Δ=min(excessu,capacityu,vflowu,v)\Delta = min(excess_u, capacity_{u,v} - flow_{u,v}), where Δ\Delta is the maximum supported flow by the edge (u,v)(u, v). The process stops when no more excess nodes exist in the flow network.

Another important feature of the algorithm is the labeling function hh, also known as the height function, which assigns each node an integer. One labeling in valid if satisfies the following conditions: hsource=Vh_{source} = |V|, hsink=0h_{sink} = 0, and huhv+1h_u \le h_v + 1. If there is an edge from node uu to node vv with positive capacity, i.e. it supports more flow. The height function tells us where to send the excess flow, and where it's needed. It's like water, it can only flow from top to bottom.

To summarize: Start with a valid preflow and a valid labeling. In each step, for every excess node, try to push the excess flow to the node's neighbors. After each step check if the flow and the labeling are still valid. If they are and there are no more paths between the sourcesource and the sinksink, it means the maximum flow has been found.

The difference between the Edmonds-Karp (or Ford-Fulkerson) and the Push-Relabel algorithm is that the former keeps a valid flow all the time and improves it while there are augmenting paths, while in the Push-Relabel there doesn't exist an augmenting path at any time, and it improves the preflow until it reaches the maximum flow.

Time complexity: O(V2E)\mathcal{O}(V^2E)

C++

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 5000;
const ll INF = 1e15;
int n, m, source, sink;
ll capacity[MAXN + 1][MAXN + 1];

Resources

Flows

StatusSourceProblem NameDifficultyTags
CSESEasy
Show TagsMax Flow

Bipartite Matching

StatusSourceProblem NameDifficultyTags
CSESEasy
Show TagsMax Flow

It's recommended that you solve the first problem - Download Speed - in the section before trying this one.

Solution 1

A bipartite graph doesn't seem like to have anything in common with a flow network, but we can shift our point of view just by adding the source connected to the nodes in set UU and the sink connected to the nodes in set VV. And that's all. Now we have a flow network where every capacity is equal to 1.

We transformed our bipartite graph into a network flow so the maximum network flow is equal to the maximum matching. Now, we can apply our favorite max flow algorithm to solve the problem!

Time Complexity: O(VE2)\mathcal{O}(VE^2)

Solution 2

However, we can do better than this. First let's define some properties of matching algorithms.

Let's say the set MM contains all the edges that the maximum matching consists of.

We define an alternating path as a path whose edges are in the matching, MM, and not in the matching, in an alternating fashion. An alternating path stars with an unmatched node and ends once it cannot append another edge while maintaining an alternating sequence.

An augmenting path is built upon the alternating path and unmatched nodes at both ends - the nodes are not included in MM.

Tha maximum matching MM can be further improved if and only if an augmenting path is found in MM, otherwise MM is the maximum matching. It may seem difficult to understand, but the main idea is as follows:

The maximum matching can be further improved as long as the alternating sequence can be extended.

For a better understanding, you can imagine the shoelaces as an alternating path in a bipartite graph - or the sneakers.

The algorithm described above is called the Hopcroft-Karp algorithm.

Here's an animation of the algorithm if you're still a bit confused:

Time Complexity: O(EV)\mathcal{O}(E\sqrt{V})

C++

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
int n, m, k;
// dist[node] = the position of node in the alternating path
vector<int> match, dist;
vector<vector<int>> g;

Dinic's Algorithm

StatusSourceProblem NameDifficultyTags
SPOJEasy
YSEasy

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!