[백준]열혈강호4(11378)

문제 링크 : [백준]열혈강호4(11378)

문제 설명

N명의 직원이 자신이 할 수 있는 일의 번호가 주어집니다.
각 일은 1명의 담당자만 필요합니다.
각 직원은 한개의 일까지 처리할 수 있습니다.
그리고 K점의 벌점이 주어지는데, 벌점을 N명의 직원에게 자유롭게 분배할 수 있습니다.
벌점을 받은 직원은 최대 벌점만큼 일을 더 처리 할 수 있습니다.
예를들어, 1번 직원이 2점의 벌점을 받았다면, 원래 처리할 수 있는 일 1개와 벌점으로 최대 2개를 더 처리할 수 있어 최대 3개까지 일을 처리 할 수 있습니다.
최대한 많은 일을 처리하게 하면 몇개의 일을 처리할 수 있는지 구하세요.

입력

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

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

출력

4

카테고리

#이분매칭

시간 복잡도 상한

O(N²)

해결 방법

1. 직원 -> 일로 이루어지는 이분 그래프가 형성됩니다.
2. 이분 그래프에서 최대한 많은 연결 관계를 이루어야하기 때문에 이분매칭을 이용하여 최대 연결 수를 구합니다.
3. K점을 N명의 사람에게 배분을 해야하는데 경우의 수가 너무 많습니다.
4. 문제에서 중요한 점은 누구에게 몇점을 분배하는지에 대한 제약사항이 없습니다. 무조건 많이 일을 처리하게만 하면 됩니다.
5. 1번 직원부터 차례대로 더이상 일을 처리할 수 없을 때까지 이분매칭을 돌리면 최대한 많은 일을 처리하는 경우를 구할 수 있습니다.

시간복잡도

O(N*N)

코드

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