백준 11378번: 열혈강호 4 (C++)

접근

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

11378번: 열혈강호 4

이전 열혈강호 문제들과 마찬가지로 이분매칭을 이용하여 문제를 해결하였다.

이전 문제와 다른 점은 각 직원들에게 해당하는 일의 수가 벌점에 의해 바뀔 수 있으며, 이 벌점은 전체 직원의 총점만 정해져있고, 어떤 직원에게 몇 점의 벌점을 주어 일의 갯수를 다르게 할지를 결정해야한다.

문제 해결은 아래와 같이 진행하였다.

1. 각 직원들의 기본 일의 수 1개까지는 벌점이 소모되지 않으므로 먼저 모두 이분매칭을 이용해 1개의 일을 지정해준다.
2. 1번 직원부터 벌점을 1점씩 추가해가면서 이분매칭을 수행하여 일을 배정한다. 벌점을 가할 때마다 벌점 K를 1씩 줄여주며, 일의 수를 1개씩 더해준다.
3. 1번 직원에 대하여 더이상 이분매칭을 수행할 수 없다면 2번 직원으로 넘어간다.
4. 주어질 수 있는 벌점이 0이 되거나 N번 직원까지 최대 벌점 및 할 수 있는 일을 모두 지정하였을 때 탐색을 종료한다.

코드

#include <cstring>
#include <iostream>
#include <vector>

using namespace std;

#define endl '\n'
#define MAX_N 2001

int N, M, K, ans;
int visited[MAX_N];
int bm[MAX_N];
vector<vector<int>> grid(MAX_N);

int dfs(int now) {
    if (visited[now]) return 0;
    visited[now] = 1;
    for (int next : grid[now]) {
        if (bm[next] == 0 || dfs(bm[next])) {
            bm[next] = now;
            return 1;
        }
    }
    return 0;
}

int main(int argc, char** argv) {
    // freopen 주석 처리
    freopen("input.txt", "r", stdin);

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> N >> M >> K;
    for (int i = 1; i <= N; i++) {
        int tn;
        cin >> tn;
        for (int j = 0; j < tn; j++) {
            int work;
            cin >> work;
            grid[i].push_back(work);
        }
    }
    // 1번부터 N번 직원까지 일을 1개씩 지정
    for (int i = 1; i <= N; i++) {
        memset(visited, 0, sizeof(visited));
        if (dfs(i)) ans++;
    }
    // 1번부터 벌점을 가하면서 일을 지정
    int index = 1;
    int k_index = N + 1;
    // 가할 수 있는 벌점이 0이 되거나 N번 직원까지 모두 탐색이 완료되면 종료
    while (0 < K && index <= N) {
        memset(visited, 0, sizeof(visited));
        grid[k_index] = grid[index];
        if (dfs(k_index)) {
            // index 번째 직원에게 일을 지정할 수 있을 때, index 번째 직원에게 벌점을 가하고 일을 지정
            ans++;
            k_index++;
            K--;
        } else {
            // index 번째 직원에게 일을 지정할 수 없을 때, index + 1 번째 직원 탐색
            index++;
        }
    }
    cout << ans << endl;

    return 0;
}

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!