Download Speed

import sys
from collections import deque

input = sys.stdin.readline
INF = float("inf")

def I():  return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def S():  return input().strip()

def flow_net(N):  # cap[a][b] = remaining capacity, nb = neighbours in BOTH directions
    return [[0] * N for _ in range(N)], [set() for _ in range(N)]

def add_edge(cap, nb, a, b, c):
    cap[a][b] += c                        # += : the same connection can be listed twice
    nb[a].add(b)
    nb[b].add(a)                          # b -> a must be searchable: it's the "undo" edge

def augment(cap, nb, s, t):  # BFS one s-t path with capacity left, push its bottleneck -> amount (0 = none)
    par = [-1] * len(cap)
    par[s] = s
    q = deque([s])
    while q and par[t] == -1:
        u = q.popleft()
        cu = cap[u]
        for v in nb[u]:
            if par[v] == -1 and cu[v] > 0:
                par[v] = u
                q.append(v)
    if par[t] == -1:
        return 0
    d, v = INF, t
    while v != s:                         # bottleneck = smallest cap on the path
        d = min(d, cap[par[v]][v])
        v = par[v]
    v = t
    while v != s:
        u = par[v]
        cap[u][v] -= d                    # use it up
        cap[v][u] += d                    # and allow undoing it later
        v = u
    return d

def maxflow(cap, nb, s, t):  # Edmonds-Karp, O(n m^2)
    flow = 0
    while True:
        d = augment(cap, nb, s, t)
        if d == 0:
            return flow
        flow += d

n, m = MI()
cap, nb = flow_net(n + 1)
for _ in range(m):
    a, b, c = MI()
    add_edge(cap, nb, a, b, c)

print(maxflow(cap, nb, 1, n))

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED