[백준]한조 대기 중(14433)

문제 링크 : [백준]한조 대기 중(14433)

문제 설명

두 팀에 각각 N명의 플레이어가 있고, 각 플레이어는 자신이 게임하고자하는 게임 캐릭터들이 주어집니다.
이때, 플레이어가 하고자하는 캐릭터들을 최대한 많이 배정했을 때, 적게 배정된 팀이 게임에서 승리하게 됩니다.
어떤 팀이 승리하는지 구하세요.

입력

N(각 팀별 사람의 수, 1 <= N <= 300)
M(게임 캐릭터 수, 1 <= M <= 300)
K1 K2(각 팀원들이 원하는 캐릭터의 수, 1 <= K1, K2 <= 500)
A_i B_i(A_i 사람이 B_i 캐릭터를 하고 싶어함)

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

출력

그만 알아보자

카테고리

#이분매칭

시간 복잡도 상한

O(N⁴)

해결 방법

1. 플레이어 -> 캐릭터으로 이루어지는 이분 그래프가 형성됩니다.
2. 이분 그래프에서 최대한 많은 연결 관계를 이루어야하기 때문에 이분매칭을 이용하여 최대 연결 수를 구합니다.
3. 두 팀의 이분매칭 결과를 비교합니다.

시간복잡도

O(N * K1 + N * K2)

코드

#include<cstdio>
#include<vector>
#include<string.h>
#define N 301
using namespace std;
int n,m,k1,k2,d[N],v[N],a,b,x,y,i;
vector<int>w[N];
int r(int p){
    if(v[p])return 0;
    v[p]=1;
    for(int x:w[p]){
        if(!d[x]||r(d[x])){
            d[x]=p;
            return 1;
        }
    }
    return 0;
}
int main(){
    scanf("%d%d%d%d",&n,&m,&k1,&k2);
    while(k1--){
        scanf("%d%d",&a,&b);
        w[a].push_back(b);
    }
    for(i=1;i<=n;i++)memset(v,0,sizeof(v)),x+=r(i);
    for(i=1;i<=n;i++)w[i].clear();
    memset(d,0,sizeof(d));
    while(k2--){
        scanf("%d%d",&a,&b);
        w[a].push_back(b);
    }
    for(i=1;i<=n;i++)memset(v,0,sizeof(v)),y+=r(i);
    printf("%s",x<y?"네 다음 힐딱이":"그만 알아보자");
}