백준 11407번: 책 구매하기 3 (C++)

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

11407번: 책 구매하기 3

---

Solved By: MCMF

 

바로 직전의 포스팅이었던 BOJ 11405번 문제보다 이 문제가 MCMF의 근본(?)같이 느껴졌습니다. 11405번을 풀었다면 쉽게 풀 수 있는 문제였습니다.

 

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

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

pair<int, int> MCMF(int source, int sink){
    int maxFlow = 0;
    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(c[now][next] - f[now][next] > 0
                && dist[now] + cost[now][next] < dist[next]){
                    dist[next] = dist[now] + cost[now][next];
                    
                    parent[next] = now;
                    
                    if(!isinQ[next]){
                        q.push(next); isinQ[next] = true;
                    }
                }
            }
        }
        
        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;
        }
        maxFlow += tempFlow;
    }
    
    return {maxFlow, minCost};
}

void networkModeling(){
    // from 사람 to SINK
    for(int i = m + 3; i <= m + n + 2; i++){
        adj[i].push_back(SINK);
        adj[SINK].push_back(i);
        cin >> c[i][SINK];
    }
    
    // from SOURCE to 서점
    for(int i = 3; i <= m + 2; i++){
        adj[SOURCE].push_back(i);
        adj[i].push_back(SOURCE);
        cin >> c[SOURCE][i];
    }
    
    // from 서점 to 사람, capacity
    for(int i = 3; i <= m + 2; i++){
        for(int j = m + 3; j <= m + n + 2; j++){
            adj[i].push_back(j);
            adj[j].push_back(i);
            cin >> c[i][j];
        }
    }
    
    // from 서점 to 사람, 비용 갱신
    for(int i = 3; i <= m + 2; i++){
        for(int j = m + 3; j <= m + n + 2; j++){
            cin >> cost[i][j];
            cost[j][i] = -cost[i][j];
        }
    }
}

int main(){
    cin >> n >> m;
    networkModeling();
    pair<int, int> result = MCMF(SOURCE, SINK);
    cout << result.first << '\n' << result.second;
    return 0;
}