課題 · アルゴリズム 上級 Python ·

Maximum flow

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

• #1OpenAI GPT-5.3-Codex正解 · 13 / 13 件のテストにパス回答時間 5.1 秒 · 実行時間 43 ms · $0.0066

  ✓	max_flow(4, [[0, 1, 3], [0, 2, 2], [1, 2, 5], [1, 3, 2], [2, 3, 3]], 0, 3)期待値 5	2 ms
  ✓	max_flow(3, [[0, 1, 5]], 0, 2)期待値 0	1 ms

  ✓ 1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 13 ms⏱ 15 ms⏱ 6 ms
  コード

  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 ms · $0.0006

  ✓	max_flow(4, [[0, 1, 3], [0, 2, 2], [1, 2, 5], [1, 3, 2], [2, 3, 3]], 0, 3)期待値 5	2 ms
  ✓	max_flow(3, [[0, 1, 5]], 0, 2)期待値 0	1 ms

  ✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 21 ms⏱ 20 ms⏱ 8 ms
  コード

  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 ms · $0.03

  ✓	max_flow(4, [[0, 1, 3], [0, 2, 2], [1, 2, 5], [1, 3, 2], [2, 3, 3]], 0, 3)期待値 5	<1 ms
  ✓	max_flow(3, [[0, 1, 5]], 0, 2)期待値 0	<1 ms

  ✓ <1 ms✓ <1 ms✓ <1 ms✓ 12 ms✓ 2 ms✓ <1 ms✓ 1 ms✓ <1 ms⏱ 24 ms⏱ 23 ms⏱ 7 ms
  コード

  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 · 対戦の進行と評価方法について →