BOJ 16707 - American Tour 링크
(2023.05.11 기준 P2)

문제

N개의 위치와 두 위치를 잇는 양방향 도로 M개가 주어진다.
위치는 여러 번 방문해도 되지만 같은 도로를 두 번 이상 방문하면 안되고, 1번 위치에서 출발하여 2번을 무조건 거쳐서 N번 위치로 간다고 했을 때의 최단 경로의 길이 출력

알고리즘

도로의 길이를 가중치로 하여금 MCMF를 돌리면 된다.

풀이

각 도로는 한번만 방문이 가능하다. 그러므로 정점 분할 기법을 도로에다가 사용하면 된다.

그리고 문제점이 있다. 1번에서 2번, 2번에서 N번으로 흐르는 유량을 source, sink를 각각 따로 잡아서 돌리면 오류가 생긴다.
2번에서 1번을 거쳐오는 도로 중 하나라도 N번으로 가는 최단 경로에 포함이 되면 유량이 거꾸로 흐르게 되어 결국 도로를 두 번 쓰게 된다.
그래서 source는 항상 같아야 한다.

도로는 양방향이다. 그러므로 1->2->N은 2->1 + 2->N과 같다.
그러므로 source를 2번 위치로 고정을 해서 1번과 N번으로 흐르는 유량을 구해주자.

코드

• C++

#include <bits/stdc++.h>
using namespace std;

const int MAX = 1000 + 10000 * 2;
const int inf = INT_MAX;

vector<int> connect[MAX];
map<int, map<int, int>> capacity;
map<int, map<int, int>> cost;

void add_edge(int u, int v, int w, int c){
    connect[u].push_back(v);
    connect[v].push_back(u);
    capacity[u][v] = w;
    capacity[v][u] = 0;
    cost[u][v] = c;
    cost[v][u] = -c;
}

int mcmf(int source, int sink){
    // SPFA
    int prev[MAX]; fill(prev, prev + MAX, -1);
    int dist[MAX]; fill(dist, dist + MAX, inf);
    bool q[MAX]; fill(q, q + MAX, false);
    deque<int> dq; dq.push_back(source); dist[source] = 0; q[source] = true;
    while (!dq.empty()){
        int here = dq.front(); dq.pop_front();
        q[here] = false;
        for (int there: connect[here])
            if (capacity[here][there] > 0 && dist[there] > dist[here] + cost[here][there]){
                dist[there] = dist[here] + cost[here][there];
                prev[there] = here;
                if (!q[there]) dq.push_back(there), q[there] = true;
            }
    }

    // 경로가 무조건 존재한다. (문제 조건)
    // 유량은 1
    int here = sink, result = 0;
    while (here != source){ // 역추적
        capacity[prev[here]][here]--;
        capacity[here][prev[here]]++;
        result += cost[prev[here]][here];
        here = prev[here];
    }

    return result;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int N, M;
    cin >> N >> M;

    // s -> road -> road_out -> e
    // e -> road -> road_out -> s
    // 총 필요한 노드는 N + M * 2
    int length = N + M * 2;

    for (int i = N, s, e, d; i < N + M; i++){
        cin >> s >> e >> d;
        add_edge(--s, i, 1, 0); // s -> road
        add_edge(--e, i, 1, 0); // e -> road
        add_edge(i, i + M, 1, d); // road -> road_out
        add_edge(i + M, s, 1, 0); // road_out -> s
        add_edge(i + M, e, 1, 0); // road_out -> e
    }

    // (0 -> 1 -> N-1) 은 (1 -> 0) + (1 -> N-1) 과 같다.
    int source = 1, result = 0;
    for (auto sink: {0, N - 1}) result += mcmf(source, sink);

    cout << result;
}

• Python

import sys; input = sys.stdin.readline
from math import inf
from collections import defaultdict, deque

def add_edge(u, v, w, c):
    connect[u].append(v)
    connect[v].append(u)
    capacity[u][v] = w
    capacity[v][u] = 0
    cost[u][v] = c
    cost[v][u] = -c

def mcmf(source, sink):
    # SPFA
    prev = [-1] * length
    distance = [inf] * length
    q = [False] * length
    queue = deque([source])
    distance[source] = 0
    q[source] = True
    while queue:
        here = queue.popleft()
        q[here] = False
        for there in connect[here]:
            if capacity[here][there] > 0 and distance[there] > distance[here] + cost[here][there]:
                distance[there] = distance[here] + cost[here][there]
                prev[there] = here
                if not q[there]:
                    queue.append(there)
                    q[there] = True

    # 경로가 무조건 존재한다. (문제 조건)
    # 유량은 1
    here = sink
    result = 0
    while here != source: # 역추적
        capacity[prev[here]][here] -= 1
        capacity[here][prev[here]] += 1
        result += cost[prev[here]][here]
        here = prev[here]

    return result

N, M = map(int, input().split())

# s -> road -> road_out -> e
# e -> road -> road_out -> s
# 총 필요한 노드는 N + M * 2
length = N + M * 2
connect = [[] for _ in range(length)]
capacity = defaultdict(dict)
cost = defaultdict(dict)

for i in range(N, N + M):
    s, e, d = map(int, input().split())
    s -= 1; e -= 1
    add_edge(s, i, 1, 0) # s -> road
    add_edge(e, i, 1, 0) # e -> road
    add_edge(i, i + M, 1, d) # road -> road_out
    add_edge(i + M, s, 1, 0) # road_out -> s
    add_edge(i + M, e, 1, 0) # road_out -> e

# (0 -> 1 -> N-1) 은 (1 -> 0) + (1 -> N-1) 과 같다.
source = 1
result = 0
for sink in [0, N - 1]:
    result += mcmf(source, sink)

print(result)