Download Speed

n, m = [int(x) for x in input().split()]
graph = [[[-1,-1] for _ in range(n)] for _ in range(n)]
max_value = 0
for _ in range(m):
    a, b, c = [int(x) for x in input().split()]
    graph[a-1][b-1] = [c, 0]
    max_value += c

def dfs(threshold, visited, x):
    visited[x] = True
    if x == n-1:
        return (True, [])
    for i, (weight, rev_weight) in enumerate(graph[x]):
        if not visited[i] and weight >= threshold:
            res = dfs(threshold, visited, i)
            if res[0]:
                res[1].append(i)
                return (True, res[1])
    return (False, [])

def scaling():
    global max_value, n

    res = dfs(max_value, [False]*n, 0)
    while not res[0] and max_value > 0:
        max_value = max_value//2
        if max_value > 0:
            res = dfs(max_value, [False]*n, 0)

    if not res[0] or res[1][0] != n-1:
        return (False, 0)
    
    res[1].append(0)
    min = float('inf')
    max = 0

    for i in range(len(res[1])-1):
        if graph[res[1][i+1]][res[1][i]][0] < min:
            min = graph[res[1][i+1]][res[1][i]][0]
    for i in range(len(res[1])-1):
        graph[res[1][i+1]][res[1][i]][0] -= min
        graph[res[1][i+1]][res[1][i]][1] += min
        if graph[res[1][i+1]][res[1][i]][1] > max:
            max = graph[res[1][i+1]][res[1][i]][1]

    return (True, max)

res = scaling()
super_max = 0
while res[0]:
    super_max += res[1]
    res = scaling()

print(super_max)

Test 1

Verdict: ACCEPTED

Test 2

Verdict: WRONG ANSWER

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: WRONG ANSWER

Test 6

Verdict: WRONG ANSWER

Test 7

Verdict: WRONG ANSWER

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: WRONG ANSWER

Test 11

Verdict: WRONG ANSWER

Test 12

Verdict: WRONG ANSWER