백준 18134번: 치삼이의 대모험 (C++)

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

18134번: 치삼이의 대모험

---

Solved By: Network Flow, MCMF

 

이 문제는 2311번(https://www.acmicpc.net/problem/2311)과 29900번(https://www.acmicpc.net/problem/22990)에서 유사한 테크닉으로 풀 수 있었습니다.

 

왕복을 해야 한다는 점에서 SOURCE로부터 시작 노드로 Capacity가 2가 되도록 Edge를 잡아주고, (2311번)

또한 전체 유량이 2가 되지 않으면 -1을 출력하게 해야 한다는 점에서 유량과 최소비용 값을 한 번에 구하도록 해주었습니다. (29900번)

 

또한, 골목길과 교차점 모두 한 번 밖에 못 지나가기 때문에 골목길은 Capacity를 1을 주고, 교차점인 정점은 정점 분할을 하여 Capacity를 1로 주었습니다.

#include <iostream>
#include <vector>
#include <queue>
#define MAX 2004
#define SOURCE 2002
#define SINK 2003
#define INF 0x3f3f3f3f
#define ll long long
using namespace std;

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

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

pair<ll, ll> flow_cost(int source, int sink){
    ll Flow = 0, Cost = 0;
    while(true){
        int parent[MAX];
        bool isinQ[MAX];
        ll 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;
        
        ll temp = INF;
        
        for(int i = sink; i != source; i = parent[i]){
            if(c[parent[i]][i] - f[parent[i]][i] < temp){
                temp = c[parent[i]][i] - f[parent[i]][i];
            }
        }
        
        Flow += temp;
        for(int i = sink; i != source; i = parent[i]){
            Cost += temp * cost[parent[i]][i];
            
            f[parent[i]][i] += temp;
            f[i][parent[i]] -= temp;
        }
    }
    
    return {Flow, Cost};
}

int main(){
    cin >> N >> M;
    
    for(int i = 1; i <= N; i++){
        // in-out
        addLine(i * 2, i * 2 + 1, 1, 0);
    }
    
    for(int i = 0; i < M; i++){
        int l, v, u; cin >> l >> v >> u;
        addLine(v * 2 + 1, u * 2, 1, l);
        addLine(u * 2 + 1, v * 2, 1, l);
    }
    
    int h, t;
    cin >> h >> t;
    addLine(SOURCE, h * 2, 2, 0);
    addLine(t * 2 + 1, SINK, 2, 0);
    
    addLine(h * 2, h * 2 + 1, 2, 0);
    addLine(t * 2, t * 2 + 1, 2, 0);
    
    auto res = flow_cost(SOURCE, SINK);
    if(res.first < 2) cout << -1;
    else cout << res.second;
}