[백준 11377번] [네트워크 플로우] 열혈강호 3

기본적으로 한 노선의 capacity를 1로 잡으면 된다.(어차피 한번 경로를 잡았을 때 해당 경로의 유량은 1일수밖에 없으므로)

또한, 이러한 성질은 하나의 경로를 잡았을 때 무조건 최대유량이 1이 될 수 밖에 없는 특성을 가지고 있다.

 

다만, 이 문제에서 독특한 지점은 K명의 직원은 2개의 일을 할 수 있다는 것인데

source에서 capacity가 K인 간선을 추가적으로 만들고, 해당하는 노드에서 모든 직원에게 capacity가 1인 간선을 만들어주면 된다.

 

대략적으로 이런 느낌으로 처리해주면 된다. 이미지 출처 : https://justicehui.github.io/ps/2019/03/17/BOJ11377/

#include <bits/stdc++.h>

#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define INF 987654321;

using namespace std;

int capacity[2003][2003] = {0}; 
int flow[2003][2003] = {0};
int N, M, K;

int networkFlow(){
    int totalFlow = 0;
    while(true){
        vector<int> parent(N + M + 3, -1);
        queue<int> q;
        parent[0] = 0;
        q.push(0);
        while(!q.empty() && parent[N + M + 1] == - 1){
            int here = q.front(); q.pop();
            for(int there = 0; there <= N + M + 2; there++){
                if(capacity[here][there] - flow[here][there] > 0 && parent[there] == -1){
                    q.push(there);
                    parent[there] = here;
                }
            }
        }

        if(parent[N + M + 1] == - 1) break; // 만족하는 루트가 없는 경우
        int amount = INF;

        for(int p = N + M + 1; p != 0; p = parent[p]){
            amount = min(capacity[parent[p]][p] - flow[parent[p]][p], amount);
        }
        for(int p = N + M + 1; p != 0; p = parent[p]){
            flow[parent[p]][p] += amount;
            flow[p][parent[p]] -= amount;
        }

        totalFlow += amount;
    }
    return totalFlow;
}

int main(void){
    fastio;
    cin >> N >> M >> K;

    // 직원과 source 사이의 capacity를 1로 조정(1~N번째 index) + 2002번째 index에 K만큼의 가중치를 줌
    for(int i = 1; i <= N; i++){
        capacity[0][i] = 1;
        capacity[N + M + 2][i] = 1;
    }
    capacity[0][N + M + 2] = K;

    // 일과 sink 사이의 capacity를 1로 조정(N+1~N+M번째 index)
    for(int i = N + 1; i <= N + M; i++){
        capacity[i][N + M + 1] = 1;
    }

    // 사람과 일을 연결지음
    for(int i = 1; i <= N; i++){
        int work_num;
        cin >> work_num;
        for(int j = 0; j < work_num; j++){
            int temp;
            cin >> temp;
            capacity[i][temp + N] = 1;
        }
    }

    cout << networkFlow() << "\n";
    return 0;
}