[백준]축사 배정(2188)

문제 링크 : [백준]축사 배정(2188)

문제 설명

N마리의 소가 자신이 가고싶어하는 축사 번호가 주어집니다.
각자 소가 자신이 가고싶어하는 축사로만 배정을 할 때, 최대한 많은 소가 축사에 배정되게 하고자 할 때, 최대 몇마리의 소가 축사에 배정이 되는지 구하세요.

입력

N(소의 수, 1 <= N <= 200)
M(축사의 수, 1 <= M <= 200)
Cn_i(i번째 소가 가고 싶어하는 축사의 수)
Cv_ij(i번째 소가 가고 싶어하는 축사 번호)

5 5
2 2 5
3 2 3 4
2 1 5
3 1 2 5
1 2

출력

4

카테고리

#이분매칭

시간 복잡도 상한

O(N³)

해결 방법

1. 소 -> 축사로 이루어지는 이분 그래프가 형성됩니다.
2. 이분 그래프에서 최대한 많은 연결 관계를 이루어야하기 때문에 이분매칭을 이용하여 최대 연결 수를 구합니다.

시간복잡도

O(N*N)

코드

#include<cstdio>
#include<vector>
#include<string.h>
using namespace std;
int n,m,d[201],v[201],e[201],i,x,y;
vector<int>w[201];
int r(int p){
    if(v[p])return 0;
    v[p]=1;
    for(int x:w[p]){
        if(!e[x]||r(e[x])){
            e[x]=p;
            return 1;
        }
    }
    return 0;
}
int main(){
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++){
        scanf("%d",&x);
        while(x--){
            scanf("%d",&y);
            w[i].push_back(y);
        }
    }
    for(x=0,i=1;i<=n;i++){
        memset(v,0,sizeof(v));
        x+=r(i);
    }
    printf("%d",x);
}