Download Speed

import sys 

from collections import deque

inp = sys.stdin.read().split()
n = int(inp[0])
m = int(inp[1])
adj = [[] for _ in range(n + 1)]
capacities  = [[0] * (n + 1) for _ in range(n + 1)]
ind = 2
for i in range(m):
    u = int(inp[ind])
    v = int(inp[ind+1])
    c = int(inp[ind+2]) 
    ind+=3

    if capacities[u][v] == 0 and capacities[v][u] == 0:
            adj[u].append(v)
            adj[v].append(u)
    capacities[u][v]+=c

def bfs(s,t,parent):
    for i in range(1,n+1):
        parent[i] = -1
    parent[s] = -2 #source is considered visited

    queue = deque([(s, float('inf'))])
    while queue:
            u, flow = queue.popleft()
            
            for v in adj[u]:
                # If v is unvisited and there is available capacity
                if parent[v] == -1 and capacities[u][v] > 0:
                    parent[v] = u
                    new_flow = min(flow, capacities[u][v])
                    
                    if v == t:
                        return new_flow
                        
                    queue.append((v, new_flow))
    return 0

max_flow = 0
parent = [-1] * (n + 1)
    
while True:
    flow = bfs(1, n, parent)
    if flow == 0:
        break
    
    max_flow += flow
    
    curr = n
    while curr != 1:
        prev = parent[curr]
        capacities[prev][curr] -= flow
        capacities[curr][prev] += flow 
        curr = prev
        
print(max_flow)

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