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

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

11405번: 책 구매하기

---

Solved By: MCMF

 

처음으로 Min Cost Max Flow알고리즘을 사용해본 문제였습니다. MCMF를 이해하고 나니 확실 유량 관련 문제는 네트워크 모델링이 차지하는 지분이 많은 것을 깨닫게 됩니다.

#include <iostream>
#include <vector>
#include <queue>
#include <memory.h>
#include <algorithm>
#define MAX 203 // 100 + 100 + 1 + 1 + 1(idx == 0)
#define SOURCE 1
#define SINK 2
#define INF 1e9
#define ll long long
using namespace std;

vector<int> adj[MAX];
int cost[MAX][MAX];
int capacity[MAX][MAX], flow[MAX][MAX];
int n, m;

ll MCMF(int source, int sink){
    ll result = 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);
        dist[source] = 0;
        isinQ[source] = true;
        
        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(capacity[now][next] - flow[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, capacity[parent[i]][i] - flow[parent[i]][i]);
        }
        
        for(int i = sink; i != source; i = parent[i]){
            result += (ll)(tempflow * cost[parent[i]][i]);
            flow[parent[i]][i] += tempflow;
            flow[i][parent[i]] -= tempflow;
        }
    }
    
    return result;
}

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 >> capacity[i][SINK];
    }
    
    // from SOURCE to 서점
    for(int i = 3; i <= m + 2; i++){
        adj[SOURCE].push_back(i);
        adj[i].push_back(SOURCE);
        cin >> capacity[SOURCE][i];
    }
    
    // from 서점 to 사람
    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);
            capacity[i][j] = INF;
            cin >> cost[i][j];
            // MCMF의 유의점: 유량의 대칭성에 의해서
            // 비용 또한 역방향 간선에 대한 비용을 갱신해줘야 함.
            cost[j][i] = -cost[i][j];
        }
    }
}

int main(){
    cin >> n >> m;
    networkModeling();
    cout << MCMF(SOURCE, SINK);
    
    return 0;
}