BOJ) 11377. 열혈강호 3

문제 :

강호네 회사에는 직원이 N명이 있고, 해야할 일이 M개가 있다. 직원은 1번부터 N번까지 번호가 매겨져 있고, 일은 1번부터 M번까지 번호가 매겨져 있다.

각 직원은 한 개의 일만 할 수 있고, 각각의 일을 담당하는 사람은 1명이어야 한다. 단, N명 중에서 K명은 일을 최대 2개할 수 있다.

각각의 직원이 할 수 있는 일의 목록이 주어졌을 때, M개의 일 중에서 최대 몇 개를 할 수 있는지 구하는 프로그램을 작성하시오

해설:

최대 유량 문제 모델을 열혈 강호 2와 만들어야 한다.

여기서 주의할 점은

SRC에서 직원들에게 N+K 만큼의 유량을 흘려보내서는 안된다는 것이다.

필자도 N+K만큼 유량을 흘려보냈다가 WA를 맞았다.

N명 중에서 K명은 일을 최대 2개 할 수 있다는 점을 잘 생각해보면

다음과 같은 모델을 생각할 수 있다.

SRC는 각 직원마다 최대 용량 1인 flow를 흘려보내고, bridge로 K만큼의 flow를 흘려보낸다

그 후 bridge는 다시 직원들에게 최대 용량 1인 flow를 흘려보내면,

N명 중 K명은 최대 일을 2개 할 수 있는 모델을 만들 수 있음을 알 수 있다.


코드:

#include <iostream>
#include <algorithm>
#include <string.h>
#include <cstdio>
using namespace std;
int map[3005][3005];
int N, M, K;
bool visited[3005];
int dfs(int p, int mn){
        //cout<<p<<" "<<mn<<"\n";
        if( p == M+N+2) return mn;
        visited[p] = 1;
        int pos = 0;
        for(int i=1; i<=M+N+2; i++){
                if(!visited[i] && map[p][i] > 0){
                        mn = min(mn, map[p][i]);
                        visited[i] = 1;
                        pos = dfs(i, mn);
                        if(pos) { map[p][i]-=pos; map[i][p]+=pos; break;}
                }
        }
        return pos;
}

int main(){
        cin>>N>>M>>K;
        map[0][1] = K;
        for(int i=2; i<=N+1; i++){
                map[0][i] = 1;
                map[1][i] = 1;
                int temp; scanf("%d",&temp);
                for(int j=0; j<temp; j++){
                        int x; scanf("%d",&x);
                        map[i][x+N+1] = 1;
                }
        }
        for(int i=N+2; i<=M+N+1; i++) map[i][M+N+2]=1;
        while(1){
                memset(visited,0,sizeof(visited));
                int pos = dfs(0, 99999999);
                if(!pos) break;
        }
        int ans = 0;
        for(int i=N+2; i<=M+N+1; i++) ans += map[M+N+2][i];
        cout<<ans;
}