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])
    
    adj = [[] for _ in range(n + 1)]
    capacity = [[0] * (n + 1) for _ in range(n + 1)]
    
    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

        if capacity[u][v] == 0 and capacity[v][u] == 0:
            adj[u].append(v)
            adj[v].append(u)
        capacity[u][v] += c
        
    source = 1
    sink = n
    max_flow = 0
    
    while True:
        parent = [-1] * (n + 1)
        parent[source] = source
        
        q = deque([source])
        
        while q:
            u = q.popleft()
            
            for v in adj[u]:
                if parent[v] == -1 and capacity[u][v] > 0:
                    parent[v] = u
                    if v == sink:
                        break
                    q.append(v)
                    
            if parent[sink] != -1:
                break
                
        if parent[sink] == -1:
            break
            
        push = float('inf')
        curr = sink
        while curr != source:
            prev = parent[curr]
            if capacity[prev][curr] < push:
                push = capacity[prev][curr]
            curr = prev
            
        curr = sink
        while curr != source:
            prev = parent[curr]
            capacity[prev][curr] -= push  
            capacity[curr][prev] += push
            curr = prev
            
        max_flow += push
        
    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