Download Speed

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

connections = []
neighbors = []
for i in range(n):
    connections.append([0 for i in range(n)])
    neighbors.append([])

max_conn = 0
for i in range(m):
    a,b,c = [int(x) for x in input().split()]
    if not(b-1 in neighbors[a-1]):
        neighbors[a-1].append(b-1)
        neighbors[b-1].append(a-1)
    connections[a-1][b-1]=c
    max_conn = max(c,max_conn)

def search(L,mini,c):
    last_summit = L[-1]
    for node in neighbors[last_summit]:
        
        if not(node in L):
            curr_connection = connections[last_summit][node]
            if curr_connection >= c:
                if node == n-1:
                    mini = min(curr_connection,mini)
                    return L+[node],mini,False
                mini = min(curr_connection,mini)
                path,mini,flag = search(L+[node],mini,c)
                if flag==False:
                    return path,mini,False
            
    return [],0,True

def find_path():
    #TODO
    c = max_conn//2
    flag = True
    while flag and c>=1:
        L,mini,flag = search([0],float('inf'),c)
        c//=2
    return L,mini

def sub_mini_from_path(path,mini):
    for i in range(len(path)-1):
        connections[path[i]][path[i+1]]-=mini
        connections[path[i+1]][path[i]]+=mini


def find_max():
    curr_max = 0
    for i in range(n):
        for node in neighbors[i]:
            if connections[i][node]>curr_max:
                curr_max = connections[i][node]
    return(curr_max)

curr_path,mini = find_path()

total_flow = mini
while curr_path:
    sub_mini_from_path(curr_path,mini)
    curr_path,mini = find_path()
    total_flow+=mini

print(total_flow)

Test 1

Verdict: ACCEPTED

Test 2

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "input/code.py", line 58, in <module>
    curr_path,mini = find_path()
  File "input/code.py", line 42, in find_path
    return L,mini
UnboundLocalError: local variable 'L' referenced before assignment

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: WRONG ANSWER

Test 6

Verdict: TIME LIMIT EXCEEDED

Test 7

Verdict: TIME LIMIT EXCEEDED

Test 8

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "input/code.py", line 58, in <module>
    curr_path,mini = find_path()
  File "input/code.py", line 42, in find_path
    return L,mini
UnboundLocalError: local variable 'L' referenced before assignment

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: WRONG ANSWER

Test 12

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "input/code.py", line 58, in <module>
    curr_path,mini = find_path()
  File "input/code.py", line 42, in find_path
    return L,mini
UnboundLocalError: local variable 'L' referenced before assignment