---
# System prepended metadata

title: Maximum flow

---

# Maximum flow

```python=
def bfs(C, F, s, t):
    queue = [s]
    paths = {s: []}
    if s == t:
        return paths[s]
    while queue:
        u = queue.pop(0)
        for v in range(len(C)):
            if (C[u][v] - F[u][v] > 0) and v not in paths:
                paths[v] = paths[u] + [(u,v)]
                if v==t:
                    return paths[v]
                queue.append(v)
    return None

def solution(entrances, exits, path):
    max = float("inf")
    n = len(path)
    s = n
    t = n+1
    for row in range(n):
        path[row].append(0)
        path[row].append(max if row in exits else 0)

    n += 2
    path.append([(max if x in entrances else 0) for x in range(n)])
    path.append([0]*n)

    F = [[0]*n for i in range(n)]

    paths = bfs(path, F, s, t)
    while paths != None:
        flow = min(path[u][v] - F[u][v] for u,v in paths)
        for u,v in paths:
            F[u][v] += flow
            F[v][u] -= flow
        paths = bfs(path, F, s, t)
    return sum(F[s][i] for i in range(n))
 
if __name__ == "__main__":

    user_inputs = input().split(" ")
    n = int(user_inputs[0])
    m = int(user_inputs[1])

    C = [[0] * n for _ in range(n)]

    entrances = [i for i in range(0, n)]
    exits = [i for i in range(0, n)]

    for _m in range(m):
        user_inputs = input().split(" ")
        u = int(user_inputs[0])-1
        v = int(user_inputs[1])-1
        c = int(user_inputs[2])

        try:
            entrances.remove(v)
        except:
            pass

        try:
            exits.remove(u)
        except:
            pass

        C[u][v] = c
    # for i, c in enumerate(C):
    #     count = 0
    #     count_col = 0
    #     for j, num in enumerate(c):
    #         # print(num)
    #         # print(C[j][i])

    #         if num == 0:
    #             count += 1

    #         if C[j][i] == 0:
    #             count_col += 1

    #     if count == len(c):
    #         exits.append(i)

    #     if count_col == n:
    #         entrances.append(i)

    # for j in range(0, n):
    #     count = 0
    #     for i in range(0, n):
    #         # print(C[i][j])

    #         if C[i][j] == 0:
    #             count += 1
    #     if count == n:
    #         entrances.append(j)

    # print(entrances)
    # print(exits)

    # graph = [
    #     [0, 0, 4, 6, 0, 0],
    #     [0, 0, 5, 2, 0, 0],
    #     [0, 0, 0, 0, 4, 4],
    #     [0, 0, 0, 0, 6, 6],
    #     [0, 0, 0, 0, 0, 0],
    #     [0, 0, 0, 0, 0, 0],
    # ]
    # print(C)

    maximumFlow = solution(entrances, exits, C)
 
    print(maximumFlow)

```