Download Speed

n, m = [int(x) for x in input().split()]

matrice = {i:[] for i in range(n+1)}
threshold = 0
for _ in range(m):
    a, b, c = [int(x) for x in input().split()]
    i1 = len(matrice[a])
    i2 = len(matrice[b])
    matrice[a].append([b,c,i2])
    matrice[b].append([a,0,i1])
    threshold += c

def dfs(node, val=float('inf')):
    if node == n:
        return val
    not_visited.remove(node)
    for i, tupl in enumerate(matrice[node]):
        next_node, poid, next_index = tupl
        if poid >= threshold and next_node in not_visited:
            res = dfs(next_node, min(val, poid))
            if res > 0:
                matrice[node][i][1] -= res
                matrice[next_node][next_index][1] += res
                return res
    return 0

ans = 0
while threshold >= 1:
    while True:
        not_visited = set(range(1,n+1))
        res = dfs(1)
        ans += res
        if res == 0:
            break
    threshold = threshold // 2

print(ans)

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