BOJ) 11375. 열혈강호

문제:

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

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

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

해설:

기본적으로 각 직원이 한 개의 일만 할 수 있다는 점을 의식하면,

직원과 일의 관계가 1대1 매칭이 된다는 것을 알 수 있다.

즉, 가능한 매칭 중에 최대 매칭을 찾으면 된다.

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

코드:

#include <iostream>
#include <cstdio>
#include <string.h>
using namespace std;
int N, M;
int aMatch[1005], bMatch[1005];
bool adj[1005][1005];
bool visited[1005];

bool dfs(int p){
        if(visited[p]) return 0;
        visited[p] = 1;
        for(int i=1; i<=M; i++){
                if(adj[p][i]){
                        if(bMatch[i] == -1 || dfs(bMatch[i])){
                                bMatch[i] = p;
                                aMatch[p] = i;
                                return 1;
                        }
                }
        }
        return 0;
}

int main(){
        cin>>N>>M;
        for(int i=1; i<=N; i++){
                int temp; scanf("%d",&temp);
                for(int j=0; j<temp; j++){
                        int tm; scanf("%d",&tm);
                        adj[i][tm] = 1;
                }
        }
        int size = 0;
        memset(bMatch,-1,sizeof(bMatch));
        for(int i=1; i<=N; i++){
                memset(visited,0,sizeof(visited));
                size += dfs(i);
        }
        printf("%d",size);
}