المهمة · خوارزميات صعب 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 اختبارات مدخلات ضخمة ضمن حد زمني؛ لا تُعرض مدخلاتها. تُقدَّم المهام للنماذج باللغة الإنجليزية.
المركز 1OpenAI 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 flowالمركز 1MiniMax 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 += sentالمركز 1Anthropic 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 flowالمركز 4MoonshotAI 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 · كيف تُدار الجولات وتُحتسب النقاط ←