[백준 2188] 축사 배정 (C++)

2188번: 축사 배정

최대 유량

---

 

주어진 입력을 그래프로 나타내 보았다.

소는 자신이 원하는 축사로만 이동할 수 있음을 나타냈다.

축사에는 소를 1마리만 들일 수 있으므로 축사에서 목적지로 1마리만 보낼 수 있다고 생각해도 무방하다.

 

위 그래프의 정점의 개수는 12개이다.

시작점이 0번, 끝점이 1번.

소들은 2번부터 6번까지, 축사는 7번부터 11번의 번호를 가지게 된다.

 

그래프는 단방향 그래프지만 음수 유량을 통해서 유량 상쇄를 구현하기 위해서 그래프는 모두 양방향으로 연결해 준다.

 

그리고 모든 간선의 용량은 1이어야 한다.

시작점에서 소 정점까지의 간선의 용량이 1 인건 자명하다. 2번부터 6번까지의 소는 한 마리씩 있기 때문이다.

축사에서 끝점까지의 간선의 용량이 1인 것도 축사에 있는 소가 최대 1마리 이므로 용량이 1이어야 한다.

 

그리고 각 번호의 소가 1마리씩 있기 때문에 소와 축사를 잇는 간선의 용량도 당연히 1이다. 한 번에 소는 1마리만 이동 가능한 것이다.

 

그래프 모델링을 마무리했고, 최대 유량 알고리즘을 수행해주면 최대 소의 마릿수를 구할 수 있다.

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#define fasti ios_base::sync_with_stdio(false); cin.tie(0);
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 1e9+7
#define pii pair<int, int>
#define MAX 403
 
typedef long long ll;
// typedef pair<int, int> pii;
 
using namespace std;
 
int N, M;
int capacity[MAX][MAX], flow[MAX][MAX];
vector<int> adj[MAX];
 
void input(){
    cin >> N >> M;
    int s, a;
    for(int i = 2; i < N+2; i++){
        cin >> s;
        adj[0].push_back(i);
        adj[i].push_back(0);
        capacity[0][i] = 1;
        for(int k = 0; k < s; k++){
            cin >> a;
            adj[i].push_back(a+N+1);
            adj[a+N+1].push_back(i);
            capacity[i][a+N+1] = 1;
        }
    }
    for(int i = 2+N; i < M+2+N; i++){
        adj[i].push_back(1);
        adj[1].push_back(i);
        capacity[i][1] = 1;
    }
}
 
void MaxFlow(int source, int sink){
    int total_flow = 0;
    
    while(true){
        vector<int> prev(MAX, -1);
        queue<int> que;
        que.push(source);
        prev[source] = source;
        
        while(!que.empty() && prev[sink] == -1){
            int now = que.front();
            que.pop();
            
            for(int i = 0; i < adj[now].size(); i++){
                int next = adj[now][i];
                if(capacity[now][next] - flow[now][next] > 0 && prev[next] == -1){
                    que.push(next);
                    prev[next] = now;
                }
            }
        }
        if(prev[sink] == -1) break;
        
        int amount = INF;
        
        for(int p = sink; p != source; p = prev[p]){
            amount = min(amount, capacity[prev[p]][p] - flow[prev[p]][p]);
        }
        for(int p = sink; p != source; p = prev[p]){
            flow[prev[p]][p] += amount;
            flow[p][prev[p]] -= amount;
        }
        total_flow += amount;
    }
    
    cout << total_flow << "\n";
}
 
void solve(){
    MaxFlow(0, 1);
}
 
int main(){
    fastio
    input();
    solve();
    
    return 0;
}
 

 

최대 유량 알고리즘을 이해하는데 하루를 거의 다 썼었다..

끝판왕 느낌이 드는 알고리즘이고 현실에서의 문제를 실제로 해결할 수 있는 알고리즘인 게 맘에 든다.

이론 자체가 어려운 만큼 이해하고 나니 진짜 재밌는 것 같다.

 

 

+ 이분 탐색으로 풀 수 있다고 한다. 그래프를 다시 보니 이분 그래프네?

코드도 더 쉽고 더 빠르게 풀 수 있는 듯하다. 공부해봐야겠다.