最大二部マッチング
#Graph #Algorithm #Bipartite_Graph #Network_Flow #BFS #DFS
Abstract
Hopcroft-Karp法は, 二部グラフ$ G = (V_1, V_2; E)に対する最大マッチング問題を解くためのアルゴリズム. 最大フロー問題に帰着させると単位ネットワークになっているため, Dinitz法で解くことで$ O(|E| \sqrt{|V|})timeで解を出力する.
Explanation
TODO 書く.
Implementation
グラフ構築
Input
グラフの各部$ V_1, V_2の頂点数 N0, N1
グラフの各有向辺の始点 p1, 終点 p2
p1 は$ V_1の, p2 は$ V_2の頂点である必要がある.
Output
グラフの隣接リスト E
Time complexity
$ O(|E|)time.
最大マッチングの計算
Input
なし
Output
グラフの最大マッチング matching
Time complexity
$ O(|E| \sqrt{|V|})time.
code:python
from collections import deque
class HopcroftKarp:
def __init__(self, N0, N1):
self.N0 = N0; self.N1 = N1
self.N = N = 2 + N0 + N1
self.E = E = [[] for _ in range(N)]
for end in range(N0): # vertex 0 is the source
v = end + 2
E0.append([v, 1, len(Ev)])
Ev.append([0, 0, len(E0) - 1])
for init in range(N1): # vertex 1 is the sink
u = init + N0 + 2
Eu.append([1, 1, len(E1)])
E1.append([u, 0, len(Eu) - 1])
def add_edge(self, p1, p2):
'''
e0 = the head vertex of e,
e1 = current capacity of e,
e2 = the index of reverse edge of e.
'''
p1 += 2; p2 += self.N0 + 2
self.Ep1.append([p2, 1, len(self.Ep2)])
self.Ep2.append([p1, 0, len(self.Ep1) - 1])
def _exist_augpath(self):
self.level = level = -1 * self.N # the level (depth) of each vertex
E = self.E
q = deque((0, 0)) # (vertex, level)
while q:
v, lv = q.popleft()
if levelv < 0: # visited v for the first time
levelv = lv
for u, cap, _ in Ev:
if cap == 0 or levelu >= 0: continue
q.append((u, lv + 1))
return level1 >= 0
def _blocking_flow(self):
s = 0; t = 1
aug_flow = 0
finished = False * self.N
parent = -1 * self.N
revs = -1 * self.N
bottleneck = -1; temp_flow = 0
level, E = self.level, self.E
stack = (s, -1, float('inf'), -1, 0) # (vertex, parent, flow, rev_idx, status)
while stack:
v, p, f, rev, st = stack.pop()
if temp_flow and v != bottleneck: continue
if st == 0 and not finishedv:
parentv = p; revsv = rev
if temp_flow: # offset
f -= temp_flow; temp_flow = 0; bottleneck = -1
if v == t: # an augment path is found
aug_flow += f
if p != -1: stack += (v, p, f, rev, 3)
continue
n_children = 0
for u, cap, rev_idx in Ev:
if cap == 0 or finishedu or levelu != levelv + 1: continue
if n_children == 0:
stack += (v, p, 0, rev, 2), (u, v, min(f, cap), rev_idx, 0)
n_children += 1
else:
stack += (v, p, 0, rev, 1), (u, v, min(f, cap), rev_idx, 0)
n_children += 1
if n_children == 0: # v is a leaf
finishedv = True
elif st == 1: # now searching
continue
elif st == 2: # search finished
finishedv = True
else: # edge update
rev_e = Evrev; e = Ep[rev_e2]
e1 -= f; rev_e1 += f
if e1 == 0: bottleneck = p
if parentp != -1: stack += [(p, parentp, f, revsp, 3)]
else: temp_flow = f
return aug_flow
def max_matching(self):
matching = 0
exist_augpath, blocking_flow = self._exist_augpath, self._blocking_flow
while True:
if not exist_augpath(): break
matching += blocking_flow()
return matching
Verification
2部マッチング
References
最大二部マッチング (Hopcroft-Karp Algorithm)
ACM-ICPC: Dinic's Algorithm
Dinic法
最大流問題
ネットワークフロー入門
T. Cormen, C. Leiserson, R. Rivest, and C. Stein, 『アルゴリズムイントロダクション 第3版』, 近代科学社, 2009.
R. E. Tarjan, 『新訳 データ構造とネットワークアルゴリズム』毎日コミュニケーションズ, 2008.
繁野麻衣子, 『ネットワーク最適化とアルゴリズム』, 朝倉書店, 2010.