My Algorithm : kopricky アルゴリズムライブラリ

kopricky アルゴリズムライブラリ

Max Flow

コードについての説明(個人的メモ)

グラフ上の ss -> tt 間最大流を高速に求めるアルゴリズム. Dinitz と綴られることも多い.

時間計算量: O(n2m)O(n2m)

コード

  1. class MaxFlow:
  2. class Edge:
  3. def __init__(self, to, cap, rev):
  4. self.to, self.cap, self.rev = to, cap, rev
  5.  
  6. def __init__(self, node_size, inf):
  7. self._node = node_size
  8. self._inf = inf
  9. self._level = [-1]*self._node
  10. self._iter = [0]*self._node
  11. self._graph = [[] for _ in range(self._node)]
  12.  
  13. def add_edge(self, from_, to, cap):
  14. self._graph[from_].append(self.Edge(to, cap, len(self._graph[to])))
  15. self._graph[to].append(self.Edge(from_, 0, len(self._graph[from_])-1))
  16.  
  17. def bfs(self, start):
  18. self._level = [-1]*self._node
  19. que = deque()
  20. self._level[start] = 0
  21. que.append(start)
  22. while que:
  23. cur_vertex = que.popleft()
  24. for e in self._graph[cur_vertex]:
  25. if e.cap > 0 > self._level[e.to]:
  26. self._level[e.to] = self._level[cur_vertex] + 1
  27. que.append(e.to)
  28.  
  29. def dfs(self, cur_vertex, end_vertex, flow):
  30. if cur_vertex == end_vertex:
  31. return flow
  32. while self._iter[cur_vertex] < len(self._graph[cur_vertex]):
  33. e = self._graph[cur_vertex][self._iter[cur_vertex]]
  34. if e.cap > 0 and self._level[cur_vertex] < self._level[e.to]:
  35. flowed = self.dfs(e.to, end_vertex, min(flow, e.cap))
  36. if flowed > 0:
  37. e.cap -= flowed
  38. self._graph[e.to][e.rev].cap += flowed
  39. return flowed
  40. self._iter[cur_vertex] += 1
  41. return 0
  42.  
  43. def solve(self, source, sink):
  44. flow = 0
  45. while True:
  46. self.bfs(source)
  47. if self._level[sink] < 0:
  48. return flow
  49. self._iter = [0]*self._node
  50. while True:
  51. f = self.dfs(source, sink, self._inf)
  52. if f == 0:
  53. break
  54. flow += f

verify 用の問題

AOJ : Maximum Flow 提出コード