TESSOKU_BOOK_ A69. Bipartite Matching
Difficulty:None
問題
N人の生徒がいる。席がN個ある。
それぞれの生徒には「この席のどれかに座りたい」といった希望がある。最大で何人の希望をかなえられるか。
解法
頂点を$ 2N+2 個用意する。
$ A_i(0 \le i<N)：$ i番目の生徒を表す。
$ B_i(0 \le i< N)：$ i番目の席を表す。
$ S：フローの始点。
$ T：フローの終点。
以下のような条件で辺を張る。
$ i番目の生徒が$ j番目の席を希望しているとき、$ A_iから$ B_jに容量1の辺を張る。
$ Sから$ A_i(0 \le i<N)に容量1の辺を貼る。これは各生徒が高々1つの席に座ることができることを表す。
$ B_i(0 \le i< N)から$ Tに容量1の辺を貼る。これはそれぞれの席に高々1人が座ることができることを表す。
$ Sから$ Tまでの最大フローが答えとなる。
実装
code:cpp
int main(){
int n;
cin >> n;
vector<string>s(n);
for(auto&i:s)cin >> i;
mf_graph<int>g(n*2+2);
int S = n*2,T = n*2+1;
for(int i = 0;i<n;i++){
for(int j = 0;j<n;j++){
g.add_edge(i,j+n,1);
}
}
g.add_edge(S,i,1);
g.add_edge(i+n,T,1);
}
cout << g.flow(S,T) << endl;
}