Download Speed

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

cap = [[0] * (n + 1) for _ in range(n + 1)]
neighbors = [[] for _ in range(n + 1)]

for _ in range(m):
    a, b, c = map(int, input().split())
    if cap[a][b] == 0 and cap[b][a] == 0:
        neighbors[a].append(b)
        neighbors[b].append(a) 
    cap[a][b] += c  

flow = 0

while n > 1:

    parent = [0] * (n + 1)
    parent[1] = -1
    queue = [1]
    for x in queue:
        for y in neighbors[x]:
            if parent[y] == 0 and cap[x][y] > 0:
                parent[y] = x
                queue.append(y)

    if parent[n] == 0:
        break

    smallest = cap[parent[n]][n]
    x = n
    while x != 1:
        smallest = min(smallest, cap[parent[x]][x])
        x = parent[x]

    x = n
    while x != 1:
        cap[parent[x]][x] -= smallest
        cap[x][parent[x]] += smallest
        x = parent[x]

    flow += smallest

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