Aufgabe · Algorithmen schwer Python ·
Maximum flow
A directed network has n nodes numbered 0..n-1 and edges [u, v, c]: a pipe from u to v with capacity c (0 <= c <= 10**9). Edges can repeat, run in both directions or be self-loops. Return the maximum flow from s to t (s != t). Up to 600 nodes and 6,000 edges.
Signatur
def max_flow(n: int, edges: list[list[int]], s: int, t: int) -> int:Beispiele
max_flow(4, [[0, 1, 3], [0, 2, 2], [1, 2, 5], [1, 3, 2], [2, 3, 3]], 0, 3) # -> 5
max_flow(3, [[0, 1, 5]], 0, 2) # -> 0Zusätzlich 8 versteckte Tests und 3 Performance-Tests mit großem Input unter Zeitlimit; deren Inputs werden nicht angezeigt. Die Aufgaben werden den Modellen auf Englisch gestellt.
Platz 1OpenAI GPT-5.3-Codexgelöst · 13 von 13 TestsAntwort in 5.1 s · Laufzeit 43 ms · $0.0066 ✓ max_flow(4, [[0, 1, 3], [0, 2, 2], [1, 2, 5], [1, 3, 2], [2, 3, 3]], 0, 3)erwartet 5 2 ms ✓ max_flow(3, [[0, 1, 5]], 0, 2)erwartet 0 1 ms ✓ 1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 13 ms⏱ 15 ms⏱ 6 msCode
from collections import deque def max_flow(n: int, edges: list[list[int]], s: int, t: int) -> int: if s == t: return 0 g = [[] for _ in range(n)] def add_edge(u: int, v: int, c: int) -> None: g[u].append([v, c, len(g[v])]) g[v].append([u, 0, len(g[u]) - 1]) for u, v, c in edges: if c > 0: add_edge(u, v, c) flow = 0 INF = 10**30 while True: level = [-1] * n level[s] = 0 q = deque([s]) while q: u = q.popleft() for v, cap, rev in g[u]: if cap > 0 and level[v] < 0: level[v] = level[u] + 1 if v == t: q.clear() break q.append(v) if level[t] < 0: break it = [0] * n def dfs(u: int, f: int) -> int: if u == t: return f gu = g[u] i = it[u] while i < len(gu): it[u] = i v, cap, rev = gu[i] if cap > 0 and level[u] + 1 == level[v]: pushed = dfs(v, f if f < cap else cap) if pushed: gu[i][1] -= pushed g[v][rev][1] += pushed return pushed i += 1 it[u] = i return 0 while True: pushed = dfs(s, INF) if not pushed: break flow += pushed return flowPlatz 1MiniMax M3.1 Flashgelöst · 13 von 13 TestsAntwort in 4.9 s · Laufzeit 57 ms · $0.0006 ✓ max_flow(4, [[0, 1, 3], [0, 2, 2], [1, 2, 5], [1, 3, 2], [2, 3, 3]], 0, 3)erwartet 5 2 ms ✓ max_flow(3, [[0, 1, 5]], 0, 2)erwartet 0 1 ms ✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 21 ms⏱ 20 ms⏱ 8 msCode
import sys sys.setrecursionlimit(10000) def max_flow(n: int, edges: list[list[int]], s: int, t: int) -> int: adj = [[] for _ in range(n)] to = [] cap = [] for u, v, c in edges: if c == 0: continue idx = len(to) to.append(v) cap.append(c) adj[u].append(idx) to.append(u) cap.append(0) adj[v].append(idx + 1) total = 0 inf = 10**30 while True: level = [-1] * n level[s] = 0 queue = [s] head = 0 while head < len(queue): u = queue[head] head += 1 next_level = level[u] + 1 for ei in adj[u]: v = to[ei] if cap[ei] > 0 and level[v] < 0: level[v] = next_level queue.append(v) if level[t] < 0: return total ptr = [0] * n def dfs(u, pushed): if u == t: return pushed au = adj[u] while ptr[u] < len(au): ei = au[ptr[u]] v = to[ei] if cap[ei] > 0 and level[v] == level[u] + 1: sent = dfs(v, min(pushed, cap[ei])) if sent: cap[ei] -= sent cap[ei ^ 1] += sent return sent ptr[u] += 1 return 0 while True: sent = dfs(s, inf) if sent == 0: break total += sentPlatz 1Anthropic Claude Opus 5.5gelöst · 13 von 13 TestsAntwort in 11 s · Laufzeit 75 ms · $0.03 ✓ max_flow(4, [[0, 1, 3], [0, 2, 2], [1, 2, 5], [1, 3, 2], [2, 3, 3]], 0, 3)erwartet 5 <1 ms ✓ max_flow(3, [[0, 1, 5]], 0, 2)erwartet 0 <1 ms ✓ <1 ms✓ <1 ms✓ <1 ms✓ 12 ms✓ 2 ms✓ <1 ms✓ 1 ms✓ <1 ms⏱ 24 ms⏱ 23 ms⏱ 7 msCode
from collections import deque def max_flow(n: int, edges: list[list[int]], s: int, t: int) -> int: # Merge parallel and antiparallel edges into one forward/backward pair. pair = {} for u, v, c in edges: if u == v or c <= 0: continue if u < v: k = (u, v) if k in pair: pair[k][0] += c else: pair[k] = [c, 0] else: k = (v, u) if k in pair: pair[k][1] += c else: pair[k] = [0, c] to = [] cap = [] adj = [[] for _ in range(n)] for (u, v), (a, b) in pair.items(): e = len(to) to.append(v); cap.append(a) to.append(u); cap.append(b) adj[u].append(e) adj[v].append(e + 1) flow = 0 while True: level = [-1] * n level[s] = 0 dq = deque([s]) while dq: u = dq.popleft() lu = level[u] + 1 for e in adj[u]: if cap[e] > 0: w = to[e] if level[w] < 0: level[w] = lu dq.append(w) if level[t] < 0: break it = [0] * n path = [] u = s while True: if u == t: f = min(cap[e] for e in path) flow += f cut = -1 for i, e in enumerate(path): cap[e] -= f cap[e ^ 1] += f if cut < 0 and cap[e] == 0: cut = i del path[cut:] u = to[path[-1]] if path else s continue au = adj[u] i = it[u] L = len(au) nl = level[u] + 1 found = False while i < L: e = au[i] if cap[e] > 0 and level[to[e]] == nl: found = True break i += 1 it[u] = i if found: path.append(e) u = to[e] else: level[u] = -1 if not path: break e = path.pop() u = to[e ^ 1] it[u] += 1 return flowPlatz 4MoonshotAI Kimi K2.7 Codenicht gelöst · 0 von 13 TestsAntwort in 63 s · $0.02 Antwort wurde abgeschnitten, bevor der Code endete
✗ max_flow(4, [[0, 1, 3], [0, 2, 2], [1, 2, 5], [1, 3, 2], [2, 3, 3]], 0, 3)erwartet 5Kein Code in der Antwort — ✗ max_flow(3, [[0, 1, 5]], 0, 2)erwartet 0Kein Code in der Antwort — ✗ Kein Code in der Antwort✗ Kein Code in der Antwort✗ Kein Code in der Antwort✗ Kein Code in der Antwort✗ Kein Code in der Antwort✗ Kein Code in der Antwort✗ Kein Code in der Antwort✗ Kein Code in der Antwort⏱ Kein Code in der Antwort⏱ Kein Code in der Antwort⏱ Kein Code in der Antwort
Token-Kosten: $0.05 · So laufen Runden und Wertung ab →