[백준/BOJ C++] 3640번 : 제독 (최소 비용 최대 유량 알고리즘)

이 포스트는 프로그래밍 문제 사이트 백준 Online Judge의 3640번 : '제독' 문제의 풀이 코드와 해설을 다루고 있습니다.

 

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

 

 

3640번 : 제독

3640번: 제독

 

시작 노드와 도착 노드만 동일하고 나머지 노드는 겹치지 않는 두 경로를 잡을 때, 두 경로의 비용이 최소가 되는 합을 구하는 문제입니다.

경로의 수가 2개이기 때문에, 시작 노드와 마지막 노드에는 Capacity를 2로 설정하고, 모든 노드들을 분할하여 in 노드와 out 노드 사이의 Capacity를 1로 잡아주면, 두 경로는 같은 노드를 중복하여 방문할 수 없도록 장치가 마련되므로 답을 구할 수 있습니다.

이 때 최소 비용을 구하는 것은 MCMF 알고리즘을 활용해서 계산해줍니다.

 

 

#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;
}

int MCMF(int Sour, int Sink) {
    int CostSum = 0;
    while(true) {
        int Prev[MAX], Cost[MAX];
        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;
                    }
                }
            }
        }
        if(Prev[Sink] == -1) break;

        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;
    while(scanf("%d", &N) != EOF) {
        scanf("%d", &M);

        fill(&Capacity[0][0], &Capacity[MAX-1][MAX], 0);
        fill(&Flow[0][0], &Flow[MAX-1][MAX], 0);
        fill(&SinCost[0][0], &SinCost[MAX-1][MAX], INF);
        for(int i=0; i<MAX; i++) vector<int>().swap(Line[i]);

        int Sour = N*2+2, Sink = N*2+3;
        AddLine(Sour, 1*2, 2, 0), AddLine(N*2+1, Sink, 2, 0);
        AddLine(1*2, 1*2+1, 2, 0), AddLine(N*2, N*2+1, 2, 0);
        for(int i=2; i<N; i++) AddLine(i*2, i*2+1, 1, 0);
        for(int i=0; i<M; i++) {
            scanf("%d %d %d", &From, &To, &Cost);
            AddLine(From*2+1, To*2, 1, Cost);
        }
        printf("%d\n", MCMF(Sour, Sink));
    }
}

 

풀이 코드는 위와 같습니다.

입력부에 EOF를 처리하는 것과 매 테스트케이스마다 배열과 벡터를 초기화해주는 과정, 그리고 시작 노드와 끝 노드의 Capacity를 2로 설정해주는 과정을 제외하고는 일반적인 MCMF 문제와 동일합니다.

 

 

 

제출해보면 188ms의 시간이 소요되고 모든 테스트케이스를 통과할 수 있습니다.