グラフ上の ss -> tt 間最大流を高速に求めるアルゴリズム. Dinitz と綴られることも多い.
時間計算量: O(n2m)O(n2m)
- class MaxFlow:
- class Edge:
- def __init__(self, to, cap, rev):
- self.to, self.cap, self.rev = to, cap, rev
- def __init__(self, node_size, inf):
- self._node = node_size
- self._inf = inf
- self._level = [-1]*self._node
- self._iter = [0]*self._node
- self._graph = [[] for _ in range(self._node)]
- def add_edge(self, from_, to, cap):
- self._graph[from_].append(self.Edge(to, cap, len(self._graph[to])))
- self._graph[to].append(self.Edge(from_, 0, len(self._graph[from_])-1))
- def bfs(self, start):
- self._level = [-1]*self._node
- que = deque()
- self._level[start] = 0
- que.append(start)
- while que:
- cur_vertex = que.popleft()
- for e in self._graph[cur_vertex]:
- if e.cap > 0 > self._level[e.to]:
- self._level[e.to] = self._level[cur_vertex] + 1
- que.append(e.to)
- def dfs(self, cur_vertex, end_vertex, flow):
- if cur_vertex == end_vertex:
- return flow
- while self._iter[cur_vertex] < len(self._graph[cur_vertex]):
- e = self._graph[cur_vertex][self._iter[cur_vertex]]
- if e.cap > 0 and self._level[cur_vertex] < self._level[e.to]:
- flowed = self.dfs(e.to, end_vertex, min(flow, e.cap))
- if flowed > 0:
- e.cap -= flowed
- self._graph[e.to][e.rev].cap += flowed
- return flowed
- self._iter[cur_vertex] += 1
- return 0
- def solve(self, source, sink):
- flow = 0
- while True:
- self.bfs(source)
- if self._level[sink] < 0:
- return flow
- self._iter = [0]*self._node
- while True:
- f = self.dfs(source, sink, self._inf)
- if f == 0:
- break
- flow += f
AOJ : Maximum Flow 提出コード