# PROBLEM LINK:

Maximum Flow

Practice

Div-2 Contest

*Author:* John Nixon

*Tester:* John Nixon

*Editorialist:* John Nixon

# DIFFICULTY:

*Medium*

# PREREQUISITES:

**Divide And Conquer**

**Ford-Fulkerson Maximum Flow**

# PROBLEM:

You are given a directed graph **G** with **N** vertices and **M** edges. The vertices are numbered from **1** to **N**. Each **edge (u, v)** has a capacity **c** associated with it. You are then given **T** different pairs of vertices **(S, D)**, and you need to find the maximum flow from vertex **S** to vertex **D**.

# QUICK EXPLANATION:

For a given graph with **N** vertices and **M** edges we need to find the maximum flow form a given vertex **S** to **D** for reference have a look in the prerequisites mentioned above ,to get an idea to solve the problem just to give a brief idea, for the given graph with the capacities of the edges , we need to calculate the maximum capacity/flow that can pass through the given pair of nodes **s** and **d**.

# EXPLANATION:

Hope youâ€™ll atleast had a look in the above prerequisites, so here comes a concept called residual graph which indicates that we can have possible valid flow from **s** to **d** so when this graph is maintained properly all we need to do is just a Breath First Search from **s** to **d** and just maintain the least capacity found in the traversal ,so that it will be the maximum possible flow for that particular pair of inputs

# SOLUTIONS:

## Setter's Solution

```
import sys
max = sys.maxsize
def bfs(s, t):
visited = [False]*n
queue = []
queue.append(s)
visited[s] = True
parent[s] = -1
while queue:
u = queue.pop()
for v in range(0, n):
if visited[v] == False and residual_graph[u][v] > 0:
if v == t:
parent[v] = u
return True
queue.append(v)
parent[v] = u
visited[v] = True
return False
def ffs(s, t):
max_flow = 0
while(bfs(s, t)):
path_flow = max
v = t
while v != s:
u = parent[v]
path_flow = min(path_flow, residual_graph[u][v])
v = parent[v]
v = t
while v != s:
u = parent[v]
residual_graph[u][v] -= path_flow
residual_graph[v][u] -= path_flow
v = parent[v]
max_flow += path_flow
return max_flow
n, m = map(int, input().split())
graph = [[0]*n for _ in range(n)]
parent = [None]*n
for _ in range(m):
u, v, c = map(int, input().split())
graph[u-1][v-1] = c
pairs = []
t = int(input())
for _ in range(t):
s, d = map(int, input().split())
residual_graph = [row[:] for row in graph]
print(ffs(s-1, d-1))
```

Feel free to share your approach here. Suggestions are always welcomed.