given the capacity source and sink of a graph computes the maximum flow from source to sink input capacity source sink output maximum flow from source to sink capacity is a twodimensional array that is vv capacityij implies the capacity of the edge from i to j if there is no edge from i to j capacityij should be zero pylint disabletoomanyarguments depth first search implementation for fordfulkerson algorithm dfs function for fordfulkerson algorithm computes maximum flow from source to sink using dfs time complexity oef e is the number of edges and f is the maximum flow in the graph computes maximum flow from source to sink using bfs time complexity ove2 v is the number of vertices and e is the number of edges finds new flow using bfs update flow array following parent starting from sink bfs function for dinic algorithm check whether sink is reachable only using edges that is not full dfs function for dinic algorithm finds new flow using edges that is not full computes maximum flow from source to sink using dinic algorithm time complexity ov2e v is the number of vertices and e is the number of edges pylint disable too many arguments depth first search implementation for ford fulkerson algorithm dfs function for ford_fulkerson algorithm computes maximum flow from source to sink using dfs time complexity o ef e is the number of edges and f is the maximum flow in the graph computes maximum flow from source to sink using bfs time complexity o v e 2 v is the number of vertices and e is the number of edges finds new flow using bfs update flow array following parent starting from sink bfs function for dinic algorithm check whether sink is reachable only using edges that is not full dfs function for dinic algorithm finds new flow using edges that is not full computes maximum flow from source to sink using dinic algorithm time complexity o v 2 e v is the number of vertices and e is the number of edges
from queue import Queue


def dfs(capacity, flow, visit, vertices, idx, sink, current_flow = 1 << 63):
    

    
    if idx == sink:
        return current_flow
    visit[idx] = True
    for nxt in range(vertices):
        if not visit[nxt] and flow[idx][nxt] < capacity[idx][nxt]:
            available_flow = min(current_flow, capacity[idx][nxt]-flow[idx][nxt])
            tmp = dfs(capacity, flow, visit, vertices, nxt, sink, available_flow)
            if tmp:
                flow[idx][nxt] += tmp
                flow[nxt][idx] -= tmp
                return tmp
    return 0

def ford_fulkerson(capacity, source, sink):
    
    vertices = len(capacity)
    ret = 0
    flow = [[0]*vertices for _ in range(vertices)]
    while True:
        visit = [False for _ in range(vertices)]
        tmp = dfs(capacity, flow, visit, vertices, source, sink)
        if tmp:
            ret += tmp
        else:
            break
    return ret

def edmonds_karp(capacity, source, sink):
    
    vertices = len(capacity)
    ret = 0
    flow = [[0]*vertices for _ in range(vertices)]
    while True:
        tmp = 0
        queue = Queue()
        visit = [False for _ in range(vertices)]
        par = [-1 for _ in range(vertices)]
        visit[source] = True
        queue.put((source, 1 << 63))
        
        while queue.qsize():
            front = queue.get()
            idx, current_flow = front
            if idx == sink:
                tmp = current_flow
                break
            for nxt in range(vertices):
                if not visit[nxt] and flow[idx][nxt] < capacity[idx][nxt]:
                    visit[nxt] = True
                    par[nxt] = idx
                    queue.put((nxt, min(current_flow, capacity[idx][nxt]-flow[idx][nxt])))
        if par[sink] == -1:
            break
        ret += tmp
        parent = par[sink]
        idx = sink
        
        while parent != -1:
            flow[parent][idx] += tmp
            flow[idx][parent] -= tmp
            idx = parent
            parent = par[parent]
    return ret

def dinic_bfs(capacity, flow, level, source, sink):
    
    vertices = len(capacity)
    queue = Queue()
    queue.put(source)
    level[source] = 0
    while queue.qsize():
        front = queue.get()
        for nxt in range(vertices):
            if level[nxt] == -1 and flow[front][nxt] < capacity[front][nxt]:
                level[nxt] = level[front] + 1
                queue.put(nxt)
    return level[sink] != -1

def dinic_dfs(capacity, flow, level, idx, sink, work, current_flow = 1 << 63):
    
    if idx == sink:
        return current_flow
    vertices = len(capacity)
    while work[idx] < vertices:
        nxt = work[idx]
        if level[nxt] == level[idx] + 1 and flow[idx][nxt] < capacity[idx][nxt]:
            available_flow = min(current_flow, capacity[idx][nxt] - flow[idx][nxt])
            tmp = dinic_dfs(capacity, flow, level, nxt, sink, work, available_flow)
            if tmp > 0:
                flow[idx][nxt] += tmp
                flow[nxt][idx] -= tmp
                return tmp
        work[idx] += 1
    return 0

def dinic(capacity, source, sink):
    
    vertices = len(capacity)
    flow = [[0]*vertices for i in range(vertices)]
    ret = 0
    while True:
        level = [-1 for i in range(vertices)]
        work = [0 for i in range(vertices)]
        if not dinic_bfs(capacity, flow, level, source, sink):
            break
        while True:
            tmp = dinic_dfs(capacity, flow, level, source, sink, work)
            if tmp > 0:
                ret += tmp
            else:
                break
    return ret