Đề bài · thuật toán khó 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.
Khai báo hàm
def max_flow(n: int, edges: list[list[int]], s: int, t: int) -> int:Ví dụ
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) # -> 0Kèm theo 8 test ẩn và 3 test dữ liệu lớn có giới hạn thời gian; dữ liệu đầu vào không được hiển thị. Đề bài được giao cho các mô hình bằng tiếng Anh.
#1OpenAI GPT-5.3-Codexđã giải · 13/13 testtrả lời trong 5.1 giây · thời gian chạy 43 ms · $0.0066 ✓ max_flow(4, [[0, 1, 3], [0, 2, 2], [1, 2, 5], [1, 3, 2], [2, 3, 3]], 0, 3)kỳ vọng 5 2 ms ✓ max_flow(3, [[0, 1, 5]], 0, 2)kỳ vọng 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 flow#1MiniMax M3.1 Flashđã giải · 13/13 testtrả lời trong 4.9 giây · thời gian chạy 57 ms · $0.0006 ✓ max_flow(4, [[0, 1, 3], [0, 2, 2], [1, 2, 5], [1, 3, 2], [2, 3, 3]], 0, 3)kỳ vọng 5 2 ms ✓ max_flow(3, [[0, 1, 5]], 0, 2)kỳ vọng 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 += sent#1Anthropic Claude Opus 5.5đã giải · 13/13 testtrả lời trong 11 giây · thời gian chạy 75 ms · $0.03 ✓ max_flow(4, [[0, 1, 3], [0, 2, 2], [1, 2, 5], [1, 3, 2], [2, 3, 3]], 0, 3)kỳ vọng 5 <1 ms ✓ max_flow(3, [[0, 1, 5]], 0, 2)kỳ vọng 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 flow#4MoonshotAI Kimi K2.7 Codechưa giải được · 0/13 testtrả lời trong 63 giây · $0.02 câu trả lời bị cắt ngang trước khi mã kết thúc
✗ max_flow(4, [[0, 1, 3], [0, 2, 2], [1, 2, 5], [1, 3, 2], [2, 3, 3]], 0, 3)kỳ vọng 5không có mã nguồn trong câu trả lời — ✗ max_flow(3, [[0, 1, 5]], 0, 2)kỳ vọng 0không có mã nguồn trong câu trả lời — ✗ không có mã nguồn trong câu trả lời✗ không có mã nguồn trong câu trả lời✗ không có mã nguồn trong câu trả lời✗ không có mã nguồn trong câu trả lời✗ không có mã nguồn trong câu trả lời✗ không có mã nguồn trong câu trả lời✗ không có mã nguồn trong câu trả lời✗ không có mã nguồn trong câu trả lời⏱ không có mã nguồn trong câu trả lời⏱ không có mã nguồn trong câu trả lời⏱ không có mã nguồn trong câu trả lời
Chi phí token: $0.05 · Cách thức thi đấu và tính điểm →