ホームに戻る
2部マッチング
// PMAX_A にペアの一方の要素数
// PMAX_B にペアのもう一方の要素数
// pa[Aの要素番号][Bの要素番号] = 1 でペア 非ペアは 0
#define PMAX_A 50
#define PMAX_B 50
#define NN (PMAX_A+PMAX_B+2)
int vv[NN][NN];
int flag[NN];
int flow(int s, int e, int f){
if(s == e)return f;
flag[s] = 1;
for(int i = 0; i < NN; i++){
if(vv[s][i] > 0 && flag[i] == 0){
int d = flow(i, e, min(f, vv[s][i]));
if(d > 0){
vv[s][i] -= d;
vv[i][s] += d;
return d;
}
}
}
return 0;
}
void ae(int from, int to, int cost){
vv[from][to] = cost;
vv[to][from] = 0;
}
int pmatch(int pa[PMAX_A][PMAX_B]){
memset(vv,-1,sizeof(vv));
for(int i = 1; i <= PMAX_A; i++){
ae(0,i,1);
}
for(int i = 0; i < PMAX_A; i++){
for(int j = 0; j < PMAX_B; j++){
if(pa[i][j] == 1){
ae(i+1,j+PMAX_A+1,1);
}
}
}
for(int i = PMAX_A+1; i <= PMAX_A+PMAX_B; i++){
ae(i,PMAX_A+PMAX_B+1,1);
}
int ans = 0;
for(;;){
memset(flag,0,sizeof(flag));
int f = flow(0, PMAX_A+PMAX_B+1, 1000000000);
if(f == 0)break;
ans += f;
}
return ans;
}
int main(){
int pa[PMAX_A][PMAX_B];
memset(pa,0,sizeof(pa));
pa[0][0] = 1;
pa[0][1] = 1;
pa[1][0] = 1;
cout << pmatch(pa) << endl;
return 0;
}