Download Speed

import sys
from collections import deque

def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return

    n = int(input_data[0])
    m = int(input_data[1])

    source = 1
    sink = n

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

    graph = [[] for _ in range(n + 1)]

    def add_edge(u, v, c):
        # Forward edge
        a = Edge(v, len(graph[v]), c)
        # Reverse edge (initial capacity 0)
        b = Edge(u, len(graph[u]), 0)
        graph[u].append(a)
        graph[v].append(b)

    idx = 2
    for _ in range(m):
        u = int(input_data[idx])
        v = int(input_data[idx + 1])
        c = int(input_data[idx + 2])
        idx += 3
        add_edge(u, v, c)

    level = [-1] * (n + 1)
    ptr = [0] * (n + 1)

    def bfs():
        nonlocal level
        level = [-1] * (n + 1)
        level[source] = 0
        q = deque([source])
        while q:
            u = q.popleft()
            for edge in graph[u]:
                if edge.cap > 0 and level[edge.to] == -1:
                    level[edge.to] = level[u] + 1
                    q.append(edge.to)
        return level[sink] != -1

    def dfs(u, pushed):
        if pushed == 0 or u == sink:
            return pushed

        for i in range(ptr[u], len(graph[u])):
            ptr[u] = i
            edge = graph[u][i]
            tr = edge.to

            if level[u] + 1 != level[tr] or edge.cap == 0:
                continue

            tr_pushed = dfs(tr, min(pushed, edge.cap))
            if tr_pushed == 0:
                continue

            edge.cap -= tr_pushed
            graph[tr][edge.rev].cap += tr_pushed
            return tr_pushed

        return 0

    max_flow = 0
    INF = float('inf')

    while bfs():
        ptr = [0] * (n + 1)
        while True:
            pushed = dfs(source, INF)
            if pushed == 0:
                break
            max_flow += pushed

    print(max_flow)

if __name__ == '__main__':
    solve()

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