Maximum-Flow-Problem-Ford-Fulkerson-Algorithm

Problem Statement:

Given a single-source single-sink flow network(directed graph), find a feasible flow through the network that is maximum among all such flows.
Your program must output the maximum flow possible as well as the final residual graph.

Assume the following:

1. Every edge has integral non-negative capacities.
   
2. Every node lies on some path from source to sink.
   

Output will be evaluated on the following points:

1. The flow returned by your program is indeed maximum.
   
2. Flow leaving the source is equal to flow arriving at the sink in the final residual graph returned by your program.
   
3. Flow is conserved at each node in the final residual graph returned by your program. Flow is conserved at a node when sum of all flows coming into the node is equal to sum of all flows leaving the node.

Input Format:

Code must read and write from/to stdin and stdout.
Do not #define any inputs, all inputs must be taken dynamically from stdin.

First line of input will contain two space separated integers 'V' and 'E' indicating the number of nodes and edges in the flow network.
'E' lines will follow each containing 3 space seperated integers describing the directed edge.
First integer denotes source node of the edge.
Second integer denotes destination node of the edge.
Third integer denotes flow capacity of the edge.

Node 0 is the source node.
Node V-1 is the sink node.

Constraints:
2 <= |V| <= 10000
1 <= |E| <= 49995000
Nodes are labelled from 0 to V-1.
Edges are labelled from 0 to E-1.

Output Format:

Output contains two components.
First is the integer denoting the maximum possible flow of the given input.
Second is a residual graph represented in the same format as the input flow network.(Output the edges in the same order as that of the input)

Sample Input:
6 9
0 1 10
0 3 10
1 2 4
1 3 2
1 4 8
2 5 10
3 4 9
4 2 6
4 5 10

Sample Output:
19
0 1 10
0 3 9
1 2 3
1 3 0
1 4 7
2 5 9
3 4 9
4 2 6
4 5 10

Explanation:
Number of Nodes = V = 6
Number of Edges = E = 9

Below is the visual representation of the input flow network.
<script async src="//embedr.flickr.com/assets/client-code.js" charset="utf-8"></script>
Below is the final residual graph indicating the max flow.
<script async src="//embedr.flickr.com/assets/client-code.js" charset="utf-8"></script>

Output characteristics:

1. The max flow of 19 is indeed the maximum possible.
   
2. Flow released from source is 19, flow received at the sink is also 19.
   
3. Flow is conserved at every node in the residual graph, i.e for each node : total incoming flow is the same as total outgoing flow.
   
   For example, consider node 4.
   Incoming flow:
   edge 1->4 = 7
   edge 3->4 = 9
   Total = 16
   Outgoing flow:
   edge 4->2 = 6
   edge 4->5 = 10
   Total = 16
   Hence, flow is conserved at node 4.