BOJ) 11376. 열혈강호 2

문제:

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

각 직원은 최대 두 개의 일을 할 수 있고, 각각의 일을 담당하는 사람은 1명이어야 한다.

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

해설:

전형적인 최대 유량 문제이다. 열혈 강호 1번이 간선의 capacity가 1이었다면, 

src에서 직원에게 주는 간선의 capacity를 2로 증가시키고 flow를 흘려보내면 정답을 구할 수 있다.

https://www.acmicpc.net/problem/11376

#include <iostream>
#include <algorithm>
#include <string.h>
#include <cstdio>
using namespace std;

int map[3005][3005];
int N, M;
bool visited[3005];

int dfs(int p, int mn){
        //cout<<p<<" "<<mn<<"\n";
        if( p == M+N+1) return mn;
        visited[p] = 1;
        int pos = 0;
        for(int i=1; i<=M+N+1; 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;
        for(int i=1; i<=N; i++){
                map[0][i] = 2;
                int temp; scanf("%d",&temp);
                for(int j=0; j<temp; j++){
                        int x; scanf("%d",&x);
                        map[i][x+N] = 1;
                }
        }
        for(int i=N+1; i<=M+N; i++) map[i][M+N+1]=1;
        while(1){
                memset(visited,0,sizeof(visited));
                int pos = dfs(0, 99999999);
                if(!pos) break;
        }
        int ans = 0;
        for(int i=N+1; i<=M+N; i++) ans += map[M+N+1][i];
        cout<<ans;
}