Download Speed

from collections import deque

n, m = [int(x) for x in input().split()]
graph = [[] for _ in range(n)]

class Edge:
    def __init__(self, to, cap, rev):
        self.to = to
        self.cap = cap
        self.rev = rev

def add_edge(frm, to, cap):
    graph[frm].append(Edge(to, cap, len(graph[to])))
    graph[to].append(Edge(frm, 0, len(graph[frm]) - 1))

def bfs(s, t, level):
    queue = deque([s])
    level[s] = 0
    while queue:
        v = queue.popleft()
        for e in graph[v]:
            if e.cap > 0 and level[e.to] < 0:
                level[e.to] = level[v] + 1
                queue.append(e.to)
    return level[t] != -1

def dfs(v, t, f, level, it):
    if v == t:
        return f
    for i in range(it[v], len(graph[v])):
        it[v] = i
        e = graph[v][i]
        if e.cap > 0 and level[v] + 1 == level[e.to]:
            d = dfs(e.to, t, min(f, e.cap), level, it)
            if d > 0:
                e.cap -= d
                graph[e.to][e.rev].cap += d
                return d
    return 0

def max_flow(s, t):
    flow = 0
    INF = 10**18
    while True:
        level = [-1] * n
        if not bfs(s, t, level):
            break
        it = [0] * n
        while True:
            f = dfs(s, t, INF, level, it)
            if f == 0:
                break
            flow += f
    return flow

for _ in range(m):
    a, b, c = map(int, input().split())
    add_edge(a - 1, b - 1, c)

print(max_flow(0, n - 1))

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