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})$ と高速に動作することが分かっている.
(注)
以下の実装で $t$ に向かう辺のみは level の下がる向きに進んでおり厳密には最短とは限らない増加道を通って更新をしているがそのような辺が
saturated した後にできる逆辺はそれ以降の $s$ -> $t$ 増加道に関与しないため "増加道がフェーズごとに狭義単調増加すること"
および
"同じフェーズで saturated されてできた逆辺を通る最短の増加道は存在しないこと" が保たれ正当である.
(コンストラクタ)
BM$(u, v)$ : $u$ が人の数, $v$ が仕事の数
(関数)
add_edge$(u,v)$ : 人 $u$ と仕事 $v$ の間に辺を追加する
solve(): 最大マッチングを求める(メンバ変数 asg に結果が格納される)
minimum_vertex_cover(): (solve() を呼び出した後に呼び出すことで)最小頂点被覆を求める
時間計算量: $\O (m \sqrt{n})$
コード
class BM {
private:
const int U, V;
vector<vector<int> > G;
vector<int> level, que, prv, rasg;
int bfs(){
int last = -1;
fill(level.begin(), level.end(), -1);
int qh = 0, qt = 0;
for(int i = 0; i < U; ++i){
if(asg[i] < 0) level[i] = 0, que[qt++] = i, prv[i] = -1;
}
while(qh < qt){
const int u = que[qh++];
if(u >= U){
const int v = rasg[u - U];
if(v >= 0) level[v] = level[u] + 1, que[qt++] = v, prv[v] = u;
else last = u;
}else{
for(const int v : G[u]){
if(level[v] < 0) level[v] = level[u] + 1, que[qt++] = v, prv[v] = u;
}
}
}
return last;
}
bool dfs(const int u){
const int tmp = level[u];
level[u] = -1;
if(u >= U){
if(rasg[u - U] < 0) return true;
else return dfs(rasg[u - U]);
}else{
for(const int v : G[u]){
if(tmp < level[v]){
if(dfs(v)){
asg[u] = v - U, rasg[v - U] = u;
return true;
}
}
}
}
return false;
}
void hint_search(int cur, int& flow){
++flow;
while(cur >= 0){
level[cur] = -1;
if(cur >= U) asg[prv[cur]] = cur - U, rasg[cur - U] = prv[cur];
cur = prv[cur];
}
}
public:
BM(const int u, const int v)
: U(u), V(v), G(U + V), level(U + V), que(U + V), prv(U + V), rasg(V, -1), asg(U, -1){}
void add_edge(const int from, const int to){
G[from].push_back(U + to);
}
// asg に左側頂点がどの右側頂点とマッチングされるかが格納される
vector<int> asg;
int solve(){
int flow = 0;
for(;;){
const int cur = bfs();
if(cur < 0) break;
hint_search(cur, flow);
for(int i = 0; i < U; ++i){
if(asg[i] < 0) flow += dfs(i);
}
}
return flow;
}
// solve() を呼び出した後に呼び出す(左側頂点 i の添字は U(右側頂点数) + i とする)
vector<int> minimum_vertex_cover(){
vector<int> mvc;
for(int i = 0; i < U; ++i){
if(level[i] < 0) mvc.push_back(i);
}
for(int i = U; i < U + V; ++i){
if(level[i] >= 0) mvc.push_back(i);
}
return mvc;
}
};
verify 用の問題
yosupo さんの Library-Checker : Matching on Bipartite Graph 提出コード