Maximum Flow

Solution

Explanation

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 augmenting path from the source (the server) to the sink (Kotivalo's computer). We use BFS to find this path.

Then, we update the weights of the edges along this augmenting path. Each edge $u$, $v$ loses weight equivalent to its capacity in the augmenting path, while each reverse edge $v$, $u$ gains this weight.

It can be proven that the total number of flow augmentations(BFS calls) is $\mathcal{O}(VE)$ and that each BFS call requires $\mathcal{O}(E)$ time.

Implementation

Time complexity: $\mathcal{O}(VE^2)$

Copy
#include <bits/stdc++.h>
using namespace std;

long long max_flow(vector<vector<int>> adj, vector<vector<long long>> capacity,
                   int source, int sink) {
	int n = adj.size();
	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 $in_u - out_u$, where $in$ is the incoming flow and $out$ 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 $u$ to node $v$, we define $\Delta = min(excess_u, capacity_{u,v} - flow_{u,v})$, where $\Delta$ is the maximum supported flow by the edge $(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 $h$, also known as the height function, which assigns each node an integer. One labeling in valid if satisfies the following conditions: $h_{source} = |V|$, $h_{sink} = 0$, and $h_u \le h_v + 1$. If there is an edge from node $u$ to node $v$ 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 $source$ and the $sink$, 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: $\mathcal{O}(V^2E)$

Copy
#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

Bipartite Matching

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 $U$ and the sink connected to the nodes in set $V$. 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: $\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 $M$ contains all the edges that the maximum matching consists of.

We define an alternating path as a path whose edges are in the matching, $M$, 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 $M$.

Tha maximum matching $M$ can be further improved if and only if an augmenting path is found in $M$, otherwise $M$ 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: $\mathcal{O}(E\sqrt{V})$

Copy
#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

Hopcroft-Karp Bipartite Matching?

Implementation

Breaking Flows

When the constraints are too high ...