Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

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 )
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
Full screen
Console