백준 11376번: 열혈강호 2 (C++)

접근

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

11376번: 열혈강호 2

열혈강호 1번 문제와 동일하게 직원에게 일을 배정하는 문제이지만 한 직원이 2개의 일을 할 수 있다는 점만 다르다. 이전 문제와 동일하게 네트워크 플로우의 최대 이분 매칭을 이용하여 문제를 풀 수 있고, 한 사람당 일을 2개 할 수 있는 점은 직원 수를 2배로 늘리는 방법을 이용하여 문제를 해결하였다.

https://ca.ramel.be/249

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

코드

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

using namespace std;

#define endl '\n'
#define MAX_N 2001

int N, 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 >> 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);
            grid[i + 1000].push_back(work);
        }
    }

    for (int i = 1; i <= N; i++) {
        memset(visited, 0, sizeof(visited));
        if (dfs(i)) ans++;
        memset(visited, 0, sizeof(visited));
        if (dfs(i + 1000)) ans++;
    }
    cout << ans << endl;

    return 0;
}

더 생각해 볼 것?

...

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