취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 11378번 문제인 열혈강호 4이다.
문제는 아래 링크를 확인하자.

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

아무 직원에게나 적절히 벌점을 분배할 수 있으므로, 정답은 (벌점 없이 일을 최대 하나씩 맡았을 때 가장 많이 할 수 있는 일의 양) 과 K와 (처리가 가능한 일의 양) 둘 중 작은 값이 된다.

직원 1~N 모두가 할줄 모르는 일을 K가 커진다고 처리하게 될 수는 없으니 말이다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

bool doable[1001];
vector<int> G[1001];
int visited[1001];
int matching[1001];

int bipartite(int current) {
    if (visited[current]) return 0;
    visited[current] = 1;
    for (auto node : G[current]) {
        if (matching[node] == 0) {
            matching[node] = current;
            return 1;
        }
        if (bipartite(matching[node])) {
            matching[node] = current;
            return 1;
        }
    }
    return 0;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int cnt = 0;
    int N, M, K; cin >> N >> M >> K;
    for (int i = 1; i <= N; i++) {
        int C; cin >> C;
        while (C--) {
            int x; cin >> x;
            if (!doable[x]) {
                doable[x] = 1;
                cnt++;
            }
            G[i].push_back(x);
        }
    }

    int ans = 0;
    for (int i = 1; i <= N; i++) {
        memset(visited, 0, sizeof(visited));
        ans += bipartite(i);
    }

    cout << min(ans + K, cnt);
}