백준 17222번: 위스키 거래 (C++)

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

17222번: 위스키 거래

---

Solved By: Max Flow

 

명진이를 Source, 주은이를 Sink로 네트워크를 모델링합니다.

명진이는 무한대로 보낼 수 있고, 주은이는 무한대로 받을 수 있습니다.

하지만, 친구들은 한 번에 받을 수 있는 용량(Capacity)이 제한되어있습니다.

 

명진이가 명진이 친구들에게로 가는 edge에서 용량은 명진이 친구들이 한 번에 받을 수 있는 양으로 용량을 할당하고,

주은이 친구들이 주은이에게로 가는 것은 주은이는 무한대로 받을 수 있기 때문에 INF로 용량을 할당합니다.

 

이어서 명진이 친구들이 보낼 수 있는 곳들이 명진, 주은, 자기 자신을 제외한 모두에게 보낼 수 있다는 것을 인지해야 합니다.

즉, 명진이 친구들은 주은이 친구들에게만 보낼 수 있다는 것이 아닙니다. 문제 조건에도 나와있듯이 명진이가 연락할 수 있는 사람의 범위는 (1 ≤ K ≤ N + M - 1)입니다.

 

이 문제를 풀기위해 각 친구들이 받을 수 있는 위스키의 양을 배열 r을 선언하여 값을 지니고, 네트워크 모델링을 하면서 r배열의 값들을 사용했습니다.

 

Key Point

• 명진이 친구들끼리도 서로 위스키를 전달할 수 있다.
• 각 친구들이 받을 수 있는 위스키의 양을 배열에 저장해 두고 모델링할 때 사용하였다.

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

int n, m;
int c[MAX][MAX], f[MAX][MAX];
int r[MAX]; // 각 친구들이 한번에 얼마나 받을 수 있는지
vector<int> adj[MAX];

int edmondsKarp(int source, int sink){
    int result = 0;
    while(true){
        vector<int> parent(MAX, -1);
        vector<int> visited(MAX, -1);
        queue<int> q;
        
        q.push(source);
        visited[source] = true;
        
        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
                    && visited[next] == -1){
                    q.push(next);
                    parent[next] = now;
                    visited[next] = 1;
                    
                    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;
    
    for(int i = 1; i <= n + m; i++){
        cin >> r[i];
    }
    
    for(int i = 1; i <= n; i++){
        adj[i].push_back(SINK);
        adj[SINK].push_back(i);
        c[i][SINK] = INF;
    }
    
    for(int i = n + 1; i <= n + m; i++){
        adj[SOURCE].push_back(i);
        adj[i].push_back(SOURCE);
        c[SOURCE][i] = r[i];
    }
    
    for(int i = n + 1; i <= n + m; i++){
        int v; cin >> v;
        for(int j = 0; j < v; j++){
            int q; cin >> q;
            adj[i].push_back(q);
            adj[q].push_back(i);
            c[i][q] = r[q];
        }
    }
    
    cout << edmondsKarp(SOURCE, SINK);
    
    return 0;
}