열혈강호 2 (feat. 백준, 11376번)

열혈강호 2
https://www.acmicpc.net/problem/11376

11376번: 열혈강호 2

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <string.h>
using namespace std;
int N, M, ans, task[1001];    // 인덱스는 일, 값은 담당 직원 번호
bool arr[1001][1001], visit[1001];
bool dfs(register int n){
    for(register int m = 1; m <= M; ++m){
        if(!arr[n][m] || visit[m])
            continue;
        visit[m] = true;
        if(!task[m] || dfs(task[m])){
            task[m] = n;
            return true;
        }
    }
    return false;
}
int main(){
    ios::sync_with_stdio(false), cin.tie(NULL);
    memset(task, 0, sizeof(task));
    memset(arr, false, sizeof(arr));
    cin >> N >> M;
    for(register int n = 1, c; n <= N; ++n){
        cin >> c;
        for(register int i = 1, m; i <= c; ++i)
            cin >> m, arr[n][m] = true;
    }
    ans = 0;
    for(register int n = 1; n <= N; ++n){
        for(register int k = 1; k <= 2; ++k){
            memset(visit, false, sizeof(visit));
            if(dfs(n))
                ++ans;
        }
    }
    cout << ans;
    return 0;
}
// *&)*@*

 

이전 "열혈강호" 문제와 동일합니다. 다만 직원 한명이 두 개의 일을 할 수 있다는 내용만 다릅니다.

열혈강호 (feat. 백준, 11375번)