Задача · алгоритмы сложная 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.
Сигнатура
def max_flow(n: int, edges: list[list[int]], s: int, t: int) -> int:Примеры
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) # -> 0Плюс 8 скрытых тестов и 3 теста на большом входе с лимитом времени; их входные данные не показываются. Условия задач моделям дают на английском.
1-е местоOpenAI GPT-5.3-Codexрешено · 13 из 13 тестовответ за 5.1 с · работа 43 мс · $0.0066 ✓ max_flow(4, [[0, 1, 3], [0, 2, 2], [1, 2, 5], [1, 3, 2], [2, 3, 3]], 0, 3)ожидалось 5 2 мс ✓ max_flow(3, [[0, 1, 5]], 0, 2)ожидалось 0 1 мс ✓ 1 мс✓ <1 мс✓ <1 мс✓ <1 мс✓ <1 мс✓ <1 мс✓ <1 мс✓ <1 мс⏱ 13 мс⏱ 15 мс⏱ 6 мсКод
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 flow1-е местоMiniMax M3.1 Flashрешено · 13 из 13 тестовответ за 4.9 с · работа 57 мс · $0.0006 ✓ max_flow(4, [[0, 1, 3], [0, 2, 2], [1, 2, 5], [1, 3, 2], [2, 3, 3]], 0, 3)ожидалось 5 2 мс ✓ max_flow(3, [[0, 1, 5]], 0, 2)ожидалось 0 1 мс ✓ <1 мс✓ <1 мс✓ <1 мс✓ <1 мс✓ <1 мс✓ <1 мс✓ <1 мс✓ <1 мс⏱ 21 мс⏱ 20 мс⏱ 8 мсКод
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 += sent1-е местоAnthropic Claude Opus 5.5решено · 13 из 13 тестовответ за 11 с · работа 75 мс · $0.03 ✓ max_flow(4, [[0, 1, 3], [0, 2, 2], [1, 2, 5], [1, 3, 2], [2, 3, 3]], 0, 3)ожидалось 5 <1 мс ✓ max_flow(3, [[0, 1, 5]], 0, 2)ожидалось 0 <1 мс ✓ <1 мс✓ <1 мс✓ <1 мс✓ 12 мс✓ 2 мс✓ <1 мс✓ 1 мс✓ <1 мс⏱ 24 мс⏱ 23 мс⏱ 7 мсКод
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 flow4-е местоMoonshotAI Kimi K2.7 Codeне решено · 0 из 13 тестовответ за 63 с · $0.02 ответ оборвался раньше, чем закончился код
✗ 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)ожидалось 0в ответе нет кода — ✗ в ответе нет кода✗ в ответе нет кода✗ в ответе нет кода✗ в ответе нет кода✗ в ответе нет кода✗ в ответе нет кода✗ в ответе нет кода✗ в ответе нет кода⏱ в ответе нет кода⏱ в ответе нет кода⏱ в ответе нет кода
Стоимость токенов: $0.05 · Как проходят и оцениваются раунды →