Download Speed

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

capacity = [[0] * (n + 1) for _ in range(n + 1)]
graph = [[] for _ in range(n + 1)]

for _ in range(m):
    a, b, c = map(int, input().split())
    if b not in graph[a]:
        graph[a].append(b)
    if a not in graph[b]:
        graph[b].append(a)
    capacity[a][b] += c

source = 1
sink = n
max_flow = 0


def dfs(u, sink, visited, capacity, graph, parent):
    if u == sink:
        return True
    visited[u] = True
    for v in graph[u]:
        if not visited[v] and capacity[u][v] > 0:
            parent[v] = u
            if dfs(v, sink, visited, capacity, graph, parent):
                return True
    return False

while True:
    visited = [False] * (n + 1)
    parent = [-1] * (n + 1)

    if not dfs(source, sink, visited, capacity, graph, parent):
        break

    path_flow = float('inf')
    v = sink
    while v != source:
        u = parent[v]
        path_flow = min(path_flow, capacity[u][v])
        v = u

    v = sink
    while v != source:
        u = parent[v]
        capacity[u][v] -= path_flow
        capacity[v][u] += path_flow
        v = u

    max_flow += path_flow

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