[백준]열혈강호3(11377)

문제 링크 : [백준]열혈강호3(11377)

문제 설명

N명의 직원이 자신이 할 수 있는 일의 번호가 주어집니다.
각 일은 1명의 담당자만 필요합니다.
각 직원은 한개의 일까지 처리할 수 있습니다.
단 K명의 직원은 2개까지 일을 처리 할 수 있습니다.
최대한 많은 일을 처리하게 하면 몇개의 일을 처리할 수 있는지 구하세요.

입력

N(직원의 수, 1 <= N <= 1,000)
M(일의의 수, 1 <= M <= 1,000)
K(2개의 일을 처리 할 수 있는 직원의 수, 1 <= K <= N)
Wn_i(i번째 직원이 처리할 수 있는 일의 수)
Wv_ij(i번째 직원이 처리 할 수 있는 일의 번호)

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

출력

4

카테고리

#이분매칭

시간 복잡도 상한

O(N²)

해결 방법

1. 직원 -> 일로 이루어지는 이분 그래프가 형성됩니다.
2. 이분 그래프에서 최대한 많은 연결 관계를 이루어야하기 때문에 이분매칭을 이용하여 최대 연결 수를 구합니다.
3. K명의 직원이 두개의 일을 처리할 수 있으므로 이 부분을 해결해야 합니다.
4. 2번으로 직원 모두가 한개의 일을 처리하는 최대 수를 구했습니다.
5. 동일하게 이분매칭을 한 번 더 돌려서 각자 추가로 몇개의 일을 처리할 수 있는지를 확인하고, 그 수가 K보다 크다면 K를 출력하고, 그렇지 않다면 구한 수를 사용하면 됩니다.

시간복잡도

O(N*N)

코드

#include<iostream>
#include<vector>
#include<string.h>
#define N 1001
using namespace std;
int n,m,k,d[N],v[N],e[N],i,x,y;
vector<int>w[N];
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(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m>>k;
    for(i=1;i<=n;i++){
        cin>>x;
        while(x--){
            cin>>y;
            w[i].push_back(y);
        }
    }
    for(x=0,i=1;i<=n;i++)memset(v,0,sizeof(v)),x+=r(i);
    for(y=0,i=1;i<=n;i++)memset(v,0,sizeof(v)),y+=r(i);
    cout<<(x+(y>k?k:y));
}