Bipartite Matching Algorithm
コードについての説明(個人的メモ)
二部グラフの最大マッチングを求めるアルゴリズム. 例えば $n$ 人の人と $m$ 個の仕事があり, それぞれの人について行うことのできる仕事が分かっていて $1$ 人が高々 $1$ つの仕事を行うというような状況を考えます.
このとき最大いくつの仕事を行うことができるか？ というような問題をこのアルゴリズムを用いて高速に解くことができます.
人と仕事に対応する $n + m$ 個の頂点と仕事ができるできないに対応する 人 → 仕事 の有向辺からなる二部グラフを考える. ここで超頂点 $s,t$ を source と sink として $s$ → 人, 仕事 → $t$ の辺を先ほどの二部グラフに加えた有向グラフ上で
$s$ → $t$ の最大流問題を解く. このときの答えが問題の答えと一致している.
最大流の計算に Dinic 法 を用いると時間計算量は普通に考えると $\O (n^2 m)$ であるがこの問題に対しては $\O(m \sqrt{n})$ と高速に動作することが分かっている.
(コンストラクタ)
BM$(u, v)$ : $u$ が人の数, $v$ が仕事の数
(関数)
add_edge$(u,v)$ : 人 $u$ と仕事 $v$ の間に辺を追加する
solve(): 最大マッチングを求める
時間計算量: $\O (m \sqrt{n})$
コード
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 self._level[e.to] < 0 < e.cap:
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
class BipartiteMatching:
def __init__(self, size1, size2):
self._u_size, self. _v_size = size1, size2
self.mf = MaxFlow(self._u_size+self. _v_size+2, min(self._u_size, self._v_size))
for i in range(self._u_size):
self.mf.add_edge(0, i+1, 1)
for i in range(self._v_size):
self.mf.add_edge(self._u_size+i+1, self._u_size+self._v_size+1, 1)
def add_edge(self, from_, to):
self.mf.add_edge(from_+1, to+self._u_size+1, 1)
def solve(self):
return self.mf.solve(0, self._u_size+self._v_size+1)
verify 用の問題
AOJ : Bipartite Matching 提出コード