Download Speed

import sys
from collections import deque

def main():
    data = sys.stdin.buffer.read().split()
    n, m = int(data[0]), int(data[1])

    # Edge arrays: edge i and i^1 are a forward/reverse pair
    to = []
    cap = []
    adj = [[] for _ in range(n + 1)]

    idx = 2
    for _ in range(m):
        a, b, c = int(data[idx]), int(data[idx + 1]), int(data[idx + 2])
        idx += 3
        adj[a].append(len(to)); to.append(b); cap.append(c)
        adj[b].append(len(to)); to.append(a); cap.append(0)

    s, t = 1, n
    flow = 0

    while True:
        # BFS for shortest augmenting path
        prev_edge = [-1] * (n + 1)
        visited = [False] * (n + 1)
        visited[s] = True
        q = deque([s])
        while q and not visited[t]:
            u = q.popleft()
            for e in adj[u]:
                v = to[e]
                if not visited[v] and cap[e] > 0:
                    visited[v] = True
                    prev_edge[v] = e
                    q.append(v)

        if not visited[t]:
            break

        # Find bottleneck along the path
        bottleneck = float('inf')
        v = t
        while v != s:
            e = prev_edge[v]
            bottleneck = min(bottleneck, cap[e])
            v = to[e ^ 1]

        # Augment
        v = t
        while v != s:
            e = prev_edge[v]
            cap[e] -= bottleneck
            cap[e ^ 1] += bottleneck
            v = to[e ^ 1]

        flow += bottleneck

    print(flow)

main()

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