백준 1258번: 문제 할당 (C++)

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

1258번: 문제 할당

---

Solved By: MCMF, Bipartite Matching

 

학생이 하나씩 문제를 맡아야 한다는 점에서 Bipartite Matching을 떠올렸습니다. 그리고, 학생에서 문제를 향해 network가 modeling 되어있다고 생각하면 MCMF를 이용해 풀 수 있습니다.

 

#include <iostream>
#include <vector>
#include <queue>
#define MAX 203
#define SOURCE 1
#define SINK 2
#define INF 1e9
using namespace std;

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

int mcmf(int source, int sink){
    int mincost = 0;
    while(1){
        queue<int> q;
        bool isinQ[MAX];
        int parent[MAX], dist[MAX];
        
        fill(parent, parent + MAX, -1);
        fill(dist, dist + MAX, INF);
        
        q.push(source);
        isinQ[source] = true;
        dist[source] = 0;
        
        while(!q.empty()){
            int now = q.front(); q.pop();
            isinQ[now] = false;
            
            for(int i = 0; i < adj[now].size(); i++){
                int next = adj[now][i];
                
                if(dist[now] + cost[now][next] < dist[next]
                && c[now][next] - f[now][next] > 0){
                    dist[next] = dist[now] + cost[now][next];
                    parent[next] = now;
                    
                    if(!isinQ[next]){
                        isinQ[next] = true;
                        q.push(next);
                    }
                }
            }
        }
        
        if(parent[sink] == -1) break;
        
        int tempflow = INF;
        
        for(int i = sink; i != source; i = parent[i]){
            tempflow = min(tempflow, c[parent[i]][i] - f[parent[i]][i]);
        }
        
        for(int i = sink; i != source; i = parent[i]){
            mincost += tempflow * cost[parent[i]][i];
            
            f[parent[i]][i] += tempflow;
            f[i][parent[i]] -= tempflow;
        }
    }
    
    return mincost;
}

int main(){
    cin >> n;
    
    // network modeling
    for(int i = 3; i <= n + 2; i++){
        for(int j = n + 3; j <= 2 * n + 2; j++){
            adj[i].push_back(j);
            adj[j].push_back(i);
            
            cin >> cost[i][j];
            cost[j][i] = -cost[i][j];
            
            c[i][j] = 1;
        }
    }
    
    for(int i = 3; i <= n + 2; i++){
        adj[SOURCE].push_back(i);
        adj[i].push_back(i);
        c[SOURCE][i] = 1;
    }
    
    for(int i = n + 3; i <= 2 * n + 2; i++){
        adj[i].push_back(SINK);
        adj[SINK].push_back(i);
        c[i][SINK] = 1;
    }
    
    cout << mcmf(SOURCE, SINK);
    
    return 0;
}