Airport

from collections import defaultdict


class FordFulkerson:
    def __init__(self, n):
        self.n = n
        self.graph = defaultdict(list)  # adjacency list of edges

    def add_edge(self, u, v, cap):
        # Forward edge: capacity cap, backward edge: capacity 0
        if cap == -1:
            cap = 100000000000
        self.graph[u].append([v, cap, len(self.graph[v])])
        self.graph[v].append([u, 0, len(self.graph[u]) - 1])

    def _dfs(self, u, t, flow, visited):
        if u == t:
            return flow
        visited[u] = True
        for i, (v, cap, rev) in enumerate(self.graph[u]):
            if not visited[v] and cap > 0:
                curr_flow = min(flow, cap)
                temp_flow = self._dfs(v, t, curr_flow, visited)
                if temp_flow > 0:
                    # Update residual capacities
                    self.graph[u][i][1] -= temp_flow
                    self.graph[v][rev][1] += temp_flow
                    return temp_flow
        return 0

    def max_flow(self, s, t):
        total = 0
        while True:
            visited = [False] * self.n
            flow = self._dfs(s, t, float("inf"), visited)
            if flow == 0:
                break
            total += flow
        return total


# Example usage:

n, m = map(int, input().split())
checkpoints = list(map(int, input().split()))
ff = FordFulkerson(n)

for _ in range(m):
    x, b = map(int, input().split())
    # Convert to zero-based indexing if needed
    if x == 1:
        ff.add_edge(x - 1, b - 1, checkpoints[b - 1])
    elif b == n:
        ff.add_edge(x - 1, b - 1, checkpoints[x - 1])
    else:
        ff.add_edge(x - 1, b - 1, checkpoints[b - 1])


s, t = 0, n - 1  # source and sink
print(ff.max_flow(s, t))

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: TIME LIMIT EXCEEDED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: WRONG ANSWER

Test 13

Verdict: WRONG ANSWER