AWC0013 E - アルバイトのシフト割り当て

Difficulty:None

問題

N人の労働者がいる。時間帯がM個ある。

それぞれの労働者には「この時間のどれかで働きたい」といった希望がある。最大で何人の希望をかなえられるか。

解法

最も基本的な #二部マッチングの問題。

頂点を$ N+M+2 個用意する。

$ A_i(0 \le i<N)：$ i番目の生徒を表す。

$ B_i(0 \le i< M)：$ i番目の席を表す。

$ S：フローの始点。

$ T：フローの終点。

以下のような条件で辺を張る。

$ i番目の労働者が$ j番目の時間帯を希望しているとき、$ A_iから$ B_jに容量1の辺を張る。

$ Sから$ A_i(0 \le i<N)に容量1の辺を貼る。これは各労働者が高々1つの時間帯で働くことができることを表す。

$ B_i(0 \le i< M)から$ Tに容量1の辺を貼る。これはそれぞれの時間帯で高々1人が労働できることを表す。

$ Sから$ Tまでの最大フローが答えとなる。

実装

code:cpp

int main(){

int n,m;

cin >> n >> m;

vector<vector<int>>s;

for(int i = 0;i<n;i++){

int k;cin >> k;

vector<int>tmp(k);

for(int j = 0;j<k;j++)cin>>tmpj;

s.push_back(tmp);

}

mf_graph<int>g(n+m+2);

int S = n+m,T = n+m+1;

for(int i = 0;i<n;i++){

for(int j:si){

g.add_edge(i,j+n-1,1);

}

g.add_edge(S,i,1);

}

for(int i = 0;i<m;i++)g.add_edge(i+n,T,1);

cout << g.flow(S,T) << endl;

}