Dinic_Algorithm

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

struct Edge {
	int v ;

	int flow ; // flow of data in edge

	int C; // capacity

	int rev ;
};

// Residual Graph
class Graph {
	int V; // number of vertex
	int *level ; // stores level of a node
	vector< Edge > *adj;
public :
	Graph(int V) {
		adj = new vector<Edge>[V];
		this->V = V;
		level = new int[V];
	}

	// add edge to the graph
	void addEdge(int u, int v, int C) {
		// Forward edge : 0 flow and C capacity
		Edge a{v, 0, C, adj[v].size()};

		// Back edge : 0 flow and 0 capacity
		Edge b{u, 0, 0, adj[u].size()};

		adj[u].push_back(a);
		adj[v].push_back(b); // reverse edge
	}

	bool BFS(int s, int t);
	int sendFlow(int s, int flow, int t, int ptr[]);
	int DinicMaxflow(int s, int t);
};

bool Graph::BFS(int s, int t) {
	for (int i = 0 ; i < V ; i++)
		level[i] = -1;

	level[s] = 0;

	list< int > q;
	q.push_back(s);

	vector<Edge>::iterator i ;

	while (!q.empty()) {
		int u = q.front();
		q.pop_front();
		for (i = adj[u].begin(); i != adj[u].end(); i++) {
			Edge &e = *i;
			if (level[e.v] < 0 && e.flow < e.C) {
				level[e.v] = level[u] + 1;
				q.push_back(e.v);
			}
		}
	}

	return level[t] < 0 ? false : true ;
}

int Graph::sendFlow(int u, int flow, int t, int start[]) {
	// Sink reached
	if (u == t)
		return flow;

	for ( ; start[u] < adj[u].size(); start[u]++) {
		// Pick next edge from adjacency list of u
		Edge &e = adj[u][start[u]];

		if (level[e.v] == level[u]+1 && e.flow < e.C) {
			// find minimum flow from u to t
			int curr_flow = min(flow, e.C - e.flow);

			int temp_flow = sendFlow(e.v, curr_flow, t, start);

			// flow is greater than zero
			if (temp_flow > 0) {
				// add flow to current edge
				e.flow += temp_flow;

				adj[e.v][e.rev].flow -= temp_flow;
				return temp_flow;
			}
		}
	}

	return 0;
}

// Returns maximum flow in graph
int Graph::DinicMaxflow(int s, int t) {
	if (s == t)
		return -1;

	int total = 0;

	while (BFS(s, t) == true) {
		int *start = new int[V+1] {0};

		// while flow is not zero in graph from S to D
		while (int flow = sendFlow(s, INT_MAX, t, start))
			total += flow;
	}

	// return maximum flow
	return total;
}

// Driver Code
int main() {
    int V,Q;

    cin >> V;
	Graph g(V);

	cin >> Q;

	while(Q--) {
	    int U,V,A;
        cin >> U >> V >> A;
        g.addEdge(U, V, A );
	}

	cout << "Maximum flow is " << g.DinicMaxflow(0, 5);
	return 0;
}