Download Speed

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

c = [[0] *(n+1) for i in range(n+1)]
g = [[] for i in range(n+1)]

for i in range(m):
    a, b, w = map(int, input().split())
    c[a][b] = c[a][b] + w
    g[a].append(b)
    g[b].append(a)

r = 0
while n > 1:
    p = {1:0}
    q = [1]

    for u in q:
        for v in g[u]:

            if c[u][v] > 0 and v not in p:
                p[v] = u
                q.append(v)

    if n not in p:
        break

    f,v = 10**18, n

    while v != 1:

        f = min(f, c[p[v]][v])
        v = p[v]

    v = n
    while v != 1:

        c[p[v]][v] =c[p[v]][v] -f
        c[v][p[v]] = c[v][p[v]]+f
        v = p[v]

    r = r+f

print(r)

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