MAXFLOW - Editorial

editorial
,
1

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. :slight_smile: