Maximum Flow

Ninja
0/200
Average time to solve is 50m
profile
Contributed by
5 upvotes
Asked in companies
UberCodenation

Problem statement

There are ‘N’ houses in the Ninja Land, numbered from 1 to N. You are given M pipes connecting the houses. ‘PIPES[i]’ is represented as [FROM, TO, CAPACITY]. Your task is to find the maximum flow of water from house 1 to house N,

For Example:

You are given ‘N’ = 4, ‘M’ = 3 and ‘PIPES’ = [[1, 2, 2], [1, 3, 4], [3, 4, 3]]. The maximum flow will be 3. The graph will look like this:

graph0

The maximum flow will be 3 because 4 units of water can flow from 1 -> 3, and 3 units of water can flow from 3 -> 4.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of the input contains a single integer 'T', representing the number of test cases.

The first line of each test case contains two space-separated integers, ‘N’ and ‘M’, representing the numbers of houses and pipes, respectively.

The next line ‘M’ lines contain three space-separated integers representing a pipe.
Output Format: 
For each test case, print the maximum flow of water from house 1 to house N.

Print the output of each test case in a separate line.
Note: 
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 10
1 <= N <= 500
1 <= M <= (N*(N-1))/2
1 <= PIPES[i][0] <= N
1 <= PIPES[i][1] <= N
1 <= PIPES[i][2] <= 500

Time Limit: 1 sec
Sample Input 1:
2
4 3
1 2 2
1 3 4
3 4 3
3 2
1 2 1
2 3 1
Sample Output 1:
3
1
Explanation of Sample Input 1:
For the first test case, the graph will look like this:

graph0

The maximum flow will be 3 because 4 units of water can flow from 1 -> 3, and 3 units of water can flow from 3 -> 4.

For the second test case, the graph will look like this:

graph0

The maximum flow will be 1 as 1 unit of water can flow from 1 -> 2 -> 3.
Sample Input 2:
2
3 2
1 2 2
1 3 3
4 4
1 2 2
1 3 2
1 3 4
3 4 3
Sample Output 2:
3
3
Hint

Use the Ford-Fulkerson algorithm.

Approaches (1)
Ford-Fulkerson

Prerequisite: Ford-Fulkerson algorithm.

 

We will use the Ford-Fulkerson algorithm to find the maximum flow. It is a greedy algorithm that computes the maximum flow in a flow network.

 

The basic idea behind the Ford-Fulkerson algorithm is that as long as there is a path from the source (start node) to the sink (end node), with available capacity on all edges in the path, we send flow along with one of the paths. Then we find another path, and so on.

 

Terminologies:

  1. Residual capacity:  Capacity of an edge after subtracting the flow from the maximum capacity. 
  2. Residual graph: Original graph with residual capacity instead of given capacities.
  3. Augmenting path: A path with available capacity.

 

To check whether a path exists from the source to the sink, we will use BFS. BFS is a traversing algorithm where you should start traversing from a start node and traverse the graphs layer-wise. We will use the ‘VISITED’ array to keep track of all the visited nodes, and if VISITED[SINK] is true, there is a path from the source to the sink.

 

Algorithm :

  • Initialize a 2D array 'GRAPH' to represent the graph.
  • Iterate 'PIPE' in 'PIPES' to create graph:
    • Initialize a variable 'FROM' with value 'PIPE.GET(0)'.
    • Initialize a variable 'TO' with value 'PIPE.GET(1)'.
    • Initialize a variable 'WEIGHT' with value 'PIPE.GET(2)'.
    • Set 'GRAPH[FROM][TO]' as ('GRAPH[FROM][TO]' + 'WEIGHT').
    • Set 'GRAPH[TO][FROM]' as ('GRAPH[TO][FROM]' + 'WEIGHT').
  • Initialize a variable 'MAXFLOW' to store maximum flow.
  • Set 'MAXFLOW' as 'FORDFULKERSON(1, 'N', 'GRAPH')'.
  • Return 'MAXFLOW'.

 

Maintain a function  ‘FORDFULKERSON(INT SOURCE, INT SINK, INT[][] GRAPH)’:

  • Initialize a 2D array 'RESIDUALGRAPH' to represent the residual graph.
  • Iterate 'I' in 0 to 'GRAPH.LENGTH':
    • Iterate 'J' in 0 to 'GRAPH.LENGTH':
      • Set 'RESIDUALGRAPH'['I']['J'] as 'GRAPH'['I']['J'].
  • Initialize an integer array 'PARENT'.
  • Initialize a variable 'MAXFLOW' with value 0.
  • Iterate while there exists a path between 'SOURCE' and 'SINK' in 'RESIDUALGRAPH':
    • Initialize a variable 'CAPACITY' with value 1000000000.
    • Initialize a variable 'T' with the value 'SINK'.
    • Iterate while 'T' is not equal to 'SOURCE':
      • Initialize a variable 'S' with value 'PARENT['T']'.
      • Set 'CAPACITY' as the minimum of 'CAPACITY' and 'RESIDUALGRAPH['S']['T']'.
      • Set 'T' as 'S'.
    • Set 'T' as 'SINK'.
    • Iterate while 'T' is not equal to 'SOURCE':
      • Initialize a variable 'S' with value 'PARENT['T']'.
      • Set 'RESIDUALGRAPH['S']['T']' AS ('RESIDUALGRAPH'['S']['T'] - 'CAPACITY').
      • Set 'T' as 'S'.
    • Set 'MAXFLOW' as ('MAXFLOW' + 'CAPACITY').
  • Return 'MAXFLOW'.
     

Maintain a function ‘BFS(INT[][] RESIDUALGRAPH, INT SRC, INT DEST, INT[] PARENT)’:

  • Initialize a boolean array 'VISITED'.
  • Intialize a Queue 'QUEUE'.
  • Add 'SRC' to 'QUEUE'.
  • Set 'PARENT['SRC']' as -1.
  • Set 'VISITED['SRC']' as true.
  • Iterate while 'QUEUE' is not empty:
    • Initialize a variable 'U' with value 'QUEUE.POLL()'.
    • Iterate 'V' in 0 to 'PARENT.LENGTH':
    • If 'VISITED['V']' is false and 'RESIDUALGRAPH['U']['V']' is greater then 0.
      • Add 'V' to 'QUEUE'.
      • Set 'PARENT['V']' as 'U'.
      • Set 'VISITED['V']' as true.
  • Return 'VISITED'['DEST']'.
Time Complexity

O(M * MAXFLOW), where 'M' denotes the number of pipes, and 'MAXFLOW' denotes the max flow.

 

The time complexity of Ford-Fulkerson is O(M * MAXFLOW). Time taken for finding augmented paths is O(M). Each path can increase the MAXFLOW by at least 1. Hence, the total space complexity is O(M * MAXFLOW).

Space Complexity

O(N + M), where 'N' denotes the number of houses, and 'M' denotes the number of pipes.
 

The space complexity is bounded by the space used in implementing Ford-Fulkerson, which is O(N + M) in the worst case. Hence, the total space complexity is O(N + M).

Code Solution
(100% EXP penalty)
Maximum Flow
Full screen
Console