[백준/BOJ C++] 10786번 : Catering (ACM-ICPC World Finals 2015 C번)

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

 

문제 출처는 ACM-ICPC World Finals 2015 C번이며, 문제 난이도는 Solved.ac 기준 Platinum II에 해당합니다.

 

 

10786번 : Catering

10786번: Catering

 

Catering Company에서 N개의 request를 받아 K개의 장비들을 적절히 이동시키며 비용을 지불한다고 할 때, 가능한 비용의 합의 최솟값을 구하는 문제입니다.

주의해야 할 점은 회사와 N개의 request 장소는 별개이므로, 1~N번 중 1번을 출발점으로 생각하면 안되고 본부 노드를 별개로 두어야 합니다.

 

 

 

문제 풀이에 대한 모식도는 위와 같습니다.

장비의 수가 Request의 수보다 많을 수도 있고, 사용하던 장비는 언제든 사용을 중단할 수 있도록 하기 위해 모든 노드를 비용이 0인 Sink로 별개의 간선으로 연결시켜주어야 합니다.

그리고 각 노드를 최대 한 번씩만 방문하도록 장치를 마련하기 위해 노드를 분할하고 그 사이의 용량을 1로 만들어줍니다.

 

문제는 모든 노드를 최소 한 번 방문하도록 해야한다는 것인데, 이것은 우선 노드를 방문했을 때(즉 분할한 노드 사이의 간선을 지나갈 때)의 비용을 아주 작은 음의 값으로 만들어주고, 노드의 수만큼만 곱해서 마지막에 다시 더해줌으로써 해결이 가능합니다.

 

 

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#define MAX 305
#define INF 100000000000
using namespace std;

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

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

long long MCMF(int Sour, int Sink) {
    long long CostSum = 0;
    while(true) {
        bool isInQueue[MAX] = {};
        int Parent[MAX] = {};
        long long Cost[MAX];
        fill(Cost, Cost+MAX, INF);
        Cost[Sour] = 0;

        queue<int> Queue;
        Queue.push(Sour);
        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];
                    Parent[Next] = Curr;
                    if(!isInQueue[Next]) {
                        Queue.push(Next);
                        isInQueue[Next] = true;
                    }
                }
            }
        }
        if(!Parent[Sink]) break;

        long long Amount = INF;
        for(int i=Sink; i!=Sour; i=Parent[i])
            Amount = min(Amount, Capacity[Parent[i]][i] - Flow[Parent[i]][i]);
        for(int i=Sink; i!=Sour; i=Parent[i]) {
            CostSum += Amount*SinCost[Parent[i]][i];
            Flow[Parent[i]][i] += Amount;
            Flow[i][Parent[i]] -= Amount;
        }
    }
    return CostSum;
}

int main() {
    int N, K, Cost;
    scanf("%d %d", &N, &K);
    int Sour = 2*N+2, Sink = 2*N+3;
    for(int i=0; i<N; i++)
        for(int j=i+1; j<=N; j++) {
            scanf("%d", &Cost);
            AddLine(2*i+1, 2*j, 1, Cost);
        }
    AddLine(Sour, 1, K, 0), AddLine(1, Sink, K, 0);
    for(int i=1; i<=N; i++) AddLine(2*i, 2*i+1, 1, -10000000000);
    for(int i=1; i<=N; i++) AddLine(2*i+1, Sink, 1, 0);
    printf("%lld", MCMF(Sour, Sink) + 10000000000*N);
}

 

풀이 코드는 위와 같고, 구현 자체는 일반적인 최소 비용 최소 유량(MCMF) 알고리즘과 동일합니다.

그리고 노드 간의 간선 연결은 위의 모식도에 나타낸 그대로 구현하였으니 모식도를 참고하면서 코드를 작성하시면 조금 더 수월할 것입니다.

 

 

 

위의 코드를 제출하면 20ms가 소요되고 정답 처리를 받습니다.