백준 9413번: 제주도 관광 (C++)

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

9413번: 제주도 관광

---

Solved By: Network Flow, MCMF

 

네트워크 문제는 항상 어떻게 모델링을 할 지에 대한 아이디어가 중요합니다.

문제를 읽어보며 어떻게 처리할지 하나씩 다루어봅시다.

 

1. 교차로, 일방통행 도로

- 교차로는 Node, 일방통행 도로는 Directed Edge로 처리하였습니다.

2. 교차로를 공유하면 안 된다.

- 노드를 한 번만 지나쳐야 합니다. 정점 분할을 통해 정점 간의 Capacity를 1로 할당해주면 되겠네요.

3. 한 교차로 쌍을 연결하는 도로의 개수가 여러 개일 수 있다.

- Edge의 Capacity를 할당하지 않고, 1을 더해가며 자주 하던 실수를 면해줍니다.

4. 두 경로를 구하라.

- PRE_SOURCE를 만들어두고, SOURCE를 통해 흐르는 Capacity를 2로 주면 되겠네요.

5. 최대 교차로 수의 합을 구하라.

- 노드를 정점 분할하여 in과 out 간의 cost를 트릭을 주어 -1 값으로 주고, MCMF를 구하면 Max Cost(== 교차로의 개수)를 구할 수 있습니다.

 

그 외에도 Edge 간의 Capacity는 1, SOURCE로부터 모든 노드로 Capacity 1, 모든 노드로부터 SINK로 Capacity 1을 주어 모델링하면 되겠습니다.

#include <iostream>
#include <vector>
#include <queue>
#define MAX 605
#define INF 1e9
#define PRE_SOURCE 602
#define SOURCE 603
#define SINK 604
using namespace std;

int T;
int N, M;
vector<int> adj[MAX];
int f[MAX][MAX], c[MAX][MAX];
int cost[MAX][MAX];

void addLine(int v, int u, int cap, int co){
    adj[v].push_back(u);
    adj[u].push_back(v);
    c[v][u] = cap;
    cost[v][u] = co;
    cost[u][v] = -co;
}

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;
        
        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]){
            result += temp * cost[parent[i]][i];
            
            f[parent[i]][i] += temp;
            f[i][parent[i]] -= temp;
        }
    }
    
    return result;
}

int main(){
    cin >> T;
    for(int t = 0; t < T; t++){
        // init
        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);
        
        cin >> N >> M;
        
        addLine(PRE_SOURCE, SOURCE, 2, 0);
        
        // in - out modeling
        // 교차로 개수를 세기 위한 in - out
        for(int i = 1; i <= N; i++){
            addLine(i * 2, i * 2 + 1, 1, -1); // in to out, 최대 비용이라 트릭을 써줌
            addLine(SOURCE, i * 2, 1, 0); // source to every node
            addLine(i * 2 + 1, SINK, 1, 0); // every node to sink
        }
        
        for(int i = 0; i < M; i++){
            int a, b; cin >> a >> b;
            addLine(a * 2 + 1, b * 2, 1, 0);
        }
        
        cout << -MCMF(PRE_SOURCE, SINK) << '\n';
    }
    
    return 0;
}