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

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

11378번: 열혈강호 4

---

Solved By: Bipartite Matching, Edmonds Karp(Max Flow)

 

이번 문제는 network modeling이 까다로웠던 문제였습니다. 제가 처음 한 실수는 SOURCE node와 people node사이에 TEMP_SOURCE node를 만들고, SOURCE와 TEMP_SOURCE 사이의 capacity를 n + k로 할당하였습니다. 그런 다음 people과 works 사이에는 1, works와 SINK 사이에는 1, TEMP_SOURCE와 people 사이에는 INF를 할당하였습니다.

 

이렇게 모델링할 경우에는 어떤 문제가 발생하냐면 다른 사람이 기본적으로 1만큼 해야 할 일을 더 많이 일을 할 수 있는 사람이 일을 하게 되어버립니다. 즉, 다른 사람은 자기가 일을 할 수 있는지 없는지에 대해 따지지도 않고, 다른 사람이 일을 할 수만 있다면 다른 사람에게 일을 처리하는 꼴이 됩니다.

 

그래서 구글링을 하여 모델링하는 방법을 찾았습니다.

SOURCE에서 people로 한 사람마다 최소한 하나의 일을 할 수 있도록 사이에 capacity를 1로 할당하고, SOURCE와 TEMP_SOURCE 사이에 벌점 k를 흘려보내고, TEMP_SOURCE와 people 사이에 k를 할당합니다.

 

이렇게 되면 한 사람당 최소한 하나의 일을 하게 할 수 있도록 하고, 벌점 k를 할 수 있는 사람들에게 최대한 많이 분배가 됩니다.

즉, 다른 사람에게 자기가 할 일을 미루어버리는 일을 초래하지 않습니다.

 

(Network Modeling 그림 첨부 예정)

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#define MAX 2004
#define SOURCE 1
#define TEMP_SOURCE 3
#define SINK 2
#define INF 1e9
using namespace std;

vector<int> adj[MAX];
int c[MAX][MAX], f[MAX][MAX];
int n, m, k;

int edmondsKarp(int source, int sink){
    int result = 0;
    while(1){
        int parent[MAX];
        fill(parent, parent + MAX, -1);
        queue<int> q;
        q.push(source);
        
        while(!q.empty()){
            int now = q.front(); q.pop();
            
            for(int i = 0; i < adj[now].size(); i++){
                int next = adj[now][i];
                
                if(c[now][next] - f[now][next] > 0
                && parent[next] == -1){
                    parent[next] = now;
                    q.push(next);
                    if(next == sink) break;
                }
            }
            if(parent[sink] != -1) break;
        }
        
        if(parent[sink] == -1) break;
        
        int temp = INF;
        
        for(int i = sink; i != source; i = parent[i]){
            temp = min(temp, c[parent[i]][i] - f[parent[i]][i]);
        }
        
        for(int i = sink; i != source; i = parent[i]){
            f[parent[i]][i] += temp;
            f[i][parent[i]] -= temp;
        }
        
        result += temp;
    }
    return result;
}

int main(){
    cin >> n >> m >> k;
    
    // SOURCE to TEMP_SOURCE
    adj[SOURCE].push_back(TEMP_SOURCE);
    adj[TEMP_SOURCE].push_back(SOURCE);
    c[SOURCE][TEMP_SOURCE] = k;
    
    // SOURCE to people nodes
    for(int i = 4; i <= n + 3; i++){
        adj[SOURCE].push_back(i);
        adj[i].push_back(SOURCE);
        c[SOURCE][i] = 1;
    }
    
    // TEMP_SOURCE to people nodes
    for(int i = 4; i <= n + 3; i++){
        adj[TEMP_SOURCE].push_back(i);
        adj[i].push_back(TEMP_SOURCE);
        c[TEMP_SOURCE][i] = k;
    }
    
    // work nodes to SINK
    for(int i = n + 4; i <= n + m + 3; i++){
        adj[i].push_back(SINK);
        adj[SINK].push_back(i);
        c[i][SINK] = 1;
    }
    
    // people nodes to work nodes
    for(int i = 4; i <= n + 3; i++){
        int v; cin >> v;
        for(int u = 0; u < v; u++){
            int j; cin >> j;
            adj[i].push_back(j + n + 3);
            adj[j + n + 3].push_back(i);
            c[i][j + n + 3] = 1;
        }
    }
    
    cout << edmondsKarp(SOURCE, SINK);
    return 0;
}