Ford_Fulkerson_Algorithm

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

int V;
int parent[1000];
int rGraph[1000][1000];
int graph[1000][1000];

bool bfs( int s, int t) {

	bool visited[V];
	memset(visited, 0, sizeof(visited));

	queue<int> q;
	q.push(s);
	visited[s] = true;
	parent[s] = -1;

	while (!q.empty()) {
		int u = q.front();
		q.pop();

		for (int v = 0; v < V; v++) {
			if (visited[v] == false && rGraph[u][v] > 0) {

				if (v == t) {
					parent[v] = u;
					return true;
				}
				q.push(v);
				parent[v] = u;
				visited[v] = true;
			}
		}
	}

	return false;
}

// Returns the maximum flow from s to t in the given graph
int fordFulkerson(int s, int t)
{
	int u, v;

	for (u = 0; u < V; u++)
		for (v = 0; v < V; v++)
			rGraph[u][v] = graph[u][v];

	int max_flow = 0;

	// Augment the flow while there is path from source to
	// sink
	while (bfs( s, t)) {

		int path_flow = INT_MAX;
		for (v = t; v != s; v = parent[v]) {
			u = parent[v];
			path_flow = min(path_flow, rGraph[u][v]);
		}

		// update residual capacities of the edges and
		// reverse edges along the path
		for (v = t; v != s; v = parent[v]) {
			u = parent[v];
			rGraph[u][v] -= path_flow;
			rGraph[v][u] += path_flow;
		}

		// Add path flow to overall flow
		max_flow += path_flow;
	}

	// Return the overall flow
	return max_flow;
}

// Driver program to test above functions
int main()
{

	cin >> V;
	for(int i=0;i<V;i++) {
        for(int j=0;j<V;j++) {
            cin >> graph[i][j];
        }
	}

	cout << "The maximum possible flow is "
		<< fordFulkerson(0, V-1);

	return 0;
}