[백준/BOJ C++] 2311번 : 왕복 여행 (최소 비용 최대 유량 알고리즘, MCMF)

이 포스트는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 2311번 : '왕복 여행' 문제의 풀이 코드와 해설을 다루고 있습니다.

 

문제 난이도는 Solved.ac 기준 Platinum II에 해당하며, 문제를 풀이하기 위해 최대 유량 알고리즘(Network Flow)와 최소 비용 최대 유량 알고리즘에 대한 이해가 필요합니다.

 

 

2311번 : 왕복 여행

 

1번 나라에서 N번 나라에 방문한 후 다시 1번 나라로 돌아올 때 걸리는 최소 비용을 구하는 문제입니다.

 

 

 

단순 최소 비용 최대 유량 알고리즘으로는 해결할 수 없는 것이, MCMF 알고리즘에서는 Cost[i][j] = -Cost[j][i]로 설정함으로써 알고리즘이 작동하였는데 여기서는 간선이 양방향 간선이므로 그러한 조건의 설정이 불가능합니다.

 

그러나 이 문제 역시 정점 분할을 통해 해결이 가능한데, 정점 분할을 하면 A_out → B_in과 B_out → A_in을 구분된 루트로 만들 수 있기 때문입니다.

따라서 각 정점을 둘로 분할하고, 위의 모식도와 같이 두 노드의 in, out 노드를 연결해준 뒤 MCMF로 루트를 2개 찾아서 그 Cost를 합쳐주면 답이 됩니다.

 

 

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#define MAX 2005
#define INF 1000000000
using namespace std;

int Capacity[MAX][MAX], Flow[MAX][MAX], SinCost[MAX][MAX];
vector<int> Line[MAX];

void AddLine(int From, int To, int Cap, int Cost) {
    Line[From].push_back(To), Line[To].push_back(From);
    Capacity[From][To] = Cap;
    SinCost[From][To] = Cost, SinCost[To][From] = -Cost;
}

long long MCMF(int Sour, int Sink) {
    int Prev[MAX], Cost[MAX], CostSum = 0;
    fill(Prev, Prev+MAX, -1);
    fill(Cost, Cost+MAX, INF);
    Cost[Sour] = 0;

    queue<int> Queue;
    Queue.push(Sour);

    bool isInQueue[MAX];
    fill(isInQueue, isInQueue+MAX, false);
    isInQueue[Sour] = true;

    while(!Queue.empty()) {
        int Curr = Queue.front();
        Queue.pop();
        isInQueue[Curr] = false;
        for(int i=0; i<Line[Curr].size(); i++) {
            int Next = Line[Curr][i];
            if(Capacity[Curr][Next] - Flow[Curr][Next] > 0
                && Cost[Curr] + SinCost[Curr][Next] < Cost[Next]) {
                Cost[Next] = Cost[Curr] + SinCost[Curr][Next];
                Prev[Next] = Curr;
                if(!isInQueue[Next]) {
                    Queue.push(Next);
                    isInQueue[Next] = true;
                }
            }
        }
    }

    for(int i=Sink; i!=Sour; i=Prev[i]) {
        CostSum += SinCost[Prev[i]][i];
        Flow[Prev[i]][i]++;
        Flow[i][Prev[i]]--;
    }
    return CostSum;
}

int main() {
    int N, M, From, To, Cost;
    scanf("%d %d", &N, &M);
    int Sour = 1*2+1, Sink = N*2;
    for(int i=1; i<=N; i++) {
        Line[i*2].push_back(i*2+1), Line[i*2+1].push_back(i*2);
        Capacity[i*2][i*2+1] = Capacity[i*2+1][i*2] = INF;
    }
    for(int i=0; i<M; i++) {
        scanf("%d %d %d", &From, &To, &Cost);
        AddLine(From*2+1, To*2, 1, Cost);
        AddLine(To*2+1, From*2, 1, Cost);
    }
    printf("%lld", MCMF(Sour, Sink) + MCMF(Sour, Sink));
}

 

위의 모식도를 풀이 코드로 구현하면 위와 같이 됩니다.

기존의 MCMF 알고리즘과 같이 모든 루트를 다 찾아서 더하는 것이 아니라, 2번의 별개의 루트 탐색으로 그 cost를 합치는 것이 중요합니다.