Download Speed

from collections import deque


class Dinic:
    def __init__(self, n):
        self.n = n
        self.adj = [[] for _ in range(n)]

    def add_edge(self, u, v, cap):
        self.adj[u].append([v, cap, len(self.adj[v])])
        self.adj[v].append([u, 0, len(self.adj[u]) - 1])  # reverse edge

    def bfs(self, s, t, level):
        for i in range(len(level)):
            level[i] = -1
        level[s] = 0
        queue = deque([s])
        while queue:
            u = queue.popleft()
            for i, (v, cap, _) in enumerate(self.adj[u]):
                if cap > 0 and level[v] < 0:
                    level[v] = level[u] + 1
                    queue.append(v)
        return level[t] >= 0

    def send_flow(self, u, t, flow, level, start):
        if u == t:
            return flow
        while start[u] < len(self.adj[u]):
            v, cap, rev = self.adj[u][start[u]]
            if cap > 0 and level[v] == level[u] + 1:
                curr_flow = min(flow, cap)
                temp_flow = self.send_flow(v, t, curr_flow, level, start)
                if temp_flow > 0:
                    self.adj[u][start[u]][1] -= temp_flow
                    self.adj[v][rev][1] += temp_flow
                    return temp_flow
            start[u] += 1
        return 0

    def max_flow(self, s, t):
        if s == t:
            return -1
        total = 0
        level = [-1] * self.n
        while self.bfs(s, t, level):
            start = [0] * self.n
            flow = self.send_flow(s, t, 10**15, level, start)
            while flow > 0:
                total += flow
                flow = self.send_flow(s, t, 10**15, level, start)
        return total


# Input reading
n, m = map(int, input().split())
dinic = Dinic(n)

for _ in range(m):
    a, b, c = map(int, input().split())
    # Convert to zero-based indexing
    dinic.add_edge(a - 1, b - 1, c)

# Compute max flow from 0 to n-1
print(dinic.max_flow(0, n - 1))

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