# MAXFLOW - Editorial

Maximum Flow
Practice
Div-2 Contest

Author: John Nixon
Tester: John Nixon
Editorialist: John Nixon

Medium

# 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.