백준 3640번: 제독 (C++)

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

3640번: 제독

---

Solved By: MCMF

 

배가 2대가 움직입니다. 이 2대는 중간에서 만나서는 안 됩니다. 어떻게 중복을 체크할 수 있을까 생각을 해보면 저번부터 네트워크 모델링에서 자주 사용하던 테크닉을 사용했습니다. 자주 쓰이므로 앞으로 Node in-out Modeling이라 하겠습니다. 노드 안에 두 개의 노드가 있다고 생각하고, 하나는 in, out으로 사용하며 in과 out을 잇는 edge의 capacity는 1입니다. 이 점을 활용하면 중복이 일어날 수 없습니다.

 

그리고, 각 테스트 케이스에서 1과 V가 SOURCE와 SINK이므로 두 노드에서는 capacity를 2로 할당해주어야 합니다.

 

(항상 네트워크 관련 문제에서 여러 테스트 케이스를 돌린다면 초기화를 조심해야 합니다.)

.#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <memory.h>
#define MAX 2004
#define pii pair<int, int>
#define INF 1e9
using namespace std;

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

int MCMF(int source, int sink){
    int result = 0;
    while(true){
        int parent[MAX];
        bool isinQ[MAX];
        int dist[MAX];
        queue<int> q;
        
        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(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]){
                        isinQ[next] = true;
                        q.push(next);
                    }
                }
            }
        }
        
        if(parent[sink] == -1) break;
        
        for(int i = sink; i != source; i = parent[i]){
            result += cost[parent[i]][i];
            
            f[parent[i]][i] += 1;
            f[i][parent[i]] -= 1;
        }
    }
    
    return result;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    //vector<int> res;
    while(cin >> v >> e){
        //if(v == 0 && e == 0) break;
        
        for(int i = 0; i < MAX; i++) adj[i].clear();
        fill(&c[0][0], &c[MAX - 1][MAX], 0);
        fill(&f[0][0], &f[MAX - 1][MAX], 0);
        fill(&cost[0][0], &cost[MAX - 1][MAX], 0);
        
        // IN: node * 2, OUT: node * 2 + 1
        for(int i = 2; i < v; i++){
            adj[i * 2].push_back(i * 2 + 1);
            adj[i * 2 + 1].push_back(i * 2);
            c[i * 2][i * 2 + 1] = 1;
        }
        
        for(int i = 0; i < e; i++){
            int a, b, w;
            cin >> a >> b >> w;
            adj[a * 2 + 1].push_back(b * 2);
            adj[b * 2].push_back(a * 2 + 1);
            c[a * 2 + 1][b * 2] = 1;
            cost[a * 2 + 1][b * 2] = w;
            cost[b * 2][a * 2 + 1] = -w;
        }
        
        int SOURCE = v * 2 + 2;
        int SINK = v * 2 + 3;
        
        adj[SOURCE].push_back(2);
        adj[2].push_back(SOURCE);
        c[SOURCE][2] = 2;
        
        adj[v * 2 + 1].push_back(SINK);
        adj[SINK].push_back(v * 2 + 1);
        c[v * 2 + 1][SINK] = 2;
        
        adj[2].push_back(3);
        adj[3].push_back(2);
        c[2][3] = 2;
        
        adj[v * 2].push_back(v * 2 + 1);
        adj[v * 2 + 1].push_back(v * 2);
        c[v * 2][v * 2 + 1] = 2;
        
        cout << MCMF(SOURCE, SINK) << '\n';
        //res.push_back(MCMF(SOURCE, 2 * v));
    }
    
    //for(int i = 0; i < res.size(); i++) cout << res[i] << ' ';
    return 0;
}