Maximum Flow - Ford-Fulkerson and Edmonds-Karp

Source : 

Link1  Link2 Link3

Code :

	/// O(VE^2)
	#include<bits/stdc++.h>
	using namespace std;
	#define pii pair<int, long long>
	#define infLL 2000000000000000000
	#define ll long long
	const int N = 2000;
	int n, m;
	vector<int>edge[N];
	ll capacity[N][N];
	ll bfs(int s, int t, vector<int> &parent)
	{
	fill(parent.begin(), parent.end(), -1);
	parent[s] = -2;
	queue<pii>q;
	q.push({s, infLL});
	while(!q.empty()) {
	int u = q.front().first;
	ll flow = q.front().second;
	q.pop();
	for(int i = 0; i < edge[u].size(); i++) {
	int v = edge[u][i];
	if(parent[v]==-1 && capacity[u][v]) {
	parent[v] = u;
	ll newFlow = min(flow, capacity[u][v]);
	if(v==t) return newFlow;
	q.push({v, newFlow});
	}
	}
	}
	return 0;
	}
	ll maxFlow(int s, int t)
	{
	ll flow = 0;
	vector<int>parent(n+1);
	ll newFlow;
	while(newFlow=bfs(s, t, parent)) {
	flow += newFlow;
	int v = t;
	while(v!=s) {
	int u = parent[v];
	capacity[u][v] -= newFlow;
	capacity[v][u] += newFlow;
	v = u;
	}
	}
	return flow;
	}
	int main()
	{
	cin>>n>>m;
	for(int i = 0; i < m; i++) {
	int u, v, w;
	cin>>u>>v>>w;
	edge[u].push_back(v);
	edge[v].push_back(u);
	capacity[u][v] = w; // one directed
	}
	int s, t;
	cin>>s>>t; /// source(s) & sink(t)
	ll ans = maxFlow(s, t);
	cout<<ans<<endl;
	return 0;
	}
	/*
	6 9
	1 2 7
	1 3 4
	3 2 3
	2 4 3
	2 5 5
	3 4 2
	4 5 3
	4 6 5
	5 6 8
	1 6
	*/

view raw edmonds_karp.cpp hosted with ❤ by GitHub

Applications :

1. Max-Flow Min-Cut Theorem : It says that the capacity of the maximum flow has to be equal to the capacity of the minimum cut.

2. Multiple Source & Sink : We will connect multiple source to a super source and multiple sink to a super sink. 

3. Node Capacity : Normally we have edge capacity. If we have node capacity then we will make there two nodes instead of one node. Like - If we have 4 nodes then we will make 1 to (1 -> 5) where there is an edge between 1 & 5.

*** Under construction...