Ford-Fulkerson法をベースに、最大フローにおける経路探索の深さ優先と幅優先の速度の違いをAOJで比較した。基本的なアルゴリズムを試したいときにAOJは便利。
幅優先を使ったときは、特にEdmonds-Karpのアルゴリズムと呼ばれ、計算量はO(VE2)である。
AOJの実行時間を比較結果は以下。思ったより差がでた。
- 深さ優先：0.99s
- 幅優先：0.03s
時間のかかっている問題（#27）をピックアップすると、フロー増加操作の繰り返し回数が以下の通り、実際結構違っていた。
- 深さ優先：1664
- 幅優先：21
コードは以下。ちなみに深さ優先はほとんど蟻本のC++を移植しただけで、幅優先は適当に組んだもの。幅優先のほうが経路のトレースバックとかは一部ナイーブな処理が残っている。
from collections import deque import sys sys.setrecursionlimit(10**7) INF = 10 ** 15 V, E = [int(v) for v in input().split()] CAP = 1 REV = 2 G = [[] for _ in range(V)] for i in range(E): u, v, c = [int(v) for v in input().split()] rv = len(G[v]) ru = len(G[u]) G[u].append([v, c, rv]) G[v].append([u, 0, ru]) def dfs(v, t): closed = [False] * V return _dfs(v, t, INF, closed) def _dfs(v, t, f, closed): if v == t: return f closed[v] = True for e in G[v]: v1 = e[0] if closed[v1] or e[CAP] <= 0: continue d = _dfs(v1, t, min(f, e[CAP]), closed) if d <= 0: continue e[CAP] -= d G[v1][e[REV]][CAP] += d return d return 0 def bfs(v0, t): if v0 == t: return INF closed = [0] * V closed[v0] = INF q = deque([v0]) path = [-1] * V path[v0] = -2 while len(q) > 0: v = q.popleft() c = closed[v] for e in G[v]: v1 = e[0] if e[CAP] <= 0: continue c1 = min(c, e[CAP]) if closed[v1] != 0: continue path[v1] = v closed[v1] = c1 if v1 == t: traceback(t, path, c1) return c1 q.append(v1) return 0 def traceback(p, path, c): p0 = p while path[p0] >= 0: p = path[p0] for e in G[p]: if e[0] != p0: continue e[CAP] -= c G[p0][e[REV]][CAP] += c break p0 = p def max_flow(s, t): flow = 0 count = 0 while True: f = bfs(s, t) #f = dfs(s, t) if f == 0: return flow flow += f count += 1 print(max_flow(0, V - 1))
