Download Speed

from collections import deque

n, m = map(int, input().split())

connections = [[0]*n for _ in range(n)]
neighbors = [[] for _ in range(n)]

for _ in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    connections[a][b] += c  # permet plusieurs arêtes entre mêmes sommets
    connections[b][a] += 0  # capacité inverse initiale = 0
    if b not in neighbors[a]:
        neighbors[a].append(b)
    if a not in neighbors[b]:
        neighbors[b].append(a)

def find_path():
    """BFS pour trouver un chemin augmentant et sa capacité minimale"""
    parent = [-1]*n
    parent[0] = -2  # source marquée
    queue = deque()
    queue.append((0, float('inf')))  # (node, capacité du chemin)
    
    while queue:
        node, flow = queue.popleft()
        for neigh in neighbors[node]:
            if parent[neigh] == -1 and connections[node][neigh] > 0:
                parent[neigh] = node
                new_flow = min(flow, connections[node][neigh])
                if neigh == n-1:
                    # retrouver le chemin
                    path = []
                    cur = n-1
                    while cur != -2:
                        path.append(cur)
                        cur = parent[cur]
                    return path[::-1], new_flow
                queue.append((neigh, new_flow))
    return None, 0

def update_path(path, flow):
    for i in range(len(path)-1):
        u = path[i]
        v = path[i+1]
        connections[u][v] -= flow
        connections[v][u] += flow

total_flow = 0
while True:
    path, flow = find_path()
    if flow == 0:
        break
    update_path(path, flow)
    total_flow += flow

print(total_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