[백준/BOJ C++] 11122번 : Train Tickets (MCMF, Diamond V)

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

 

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

 

 

11122번 : Train Tickets

11122번: Train Tickets

 

기차가 1번 역에서 출발하여 모든 자연수 번호의 역을 지나며 N번 역까지 이동하며, 이 때 기차의 정원은 P명이며 일시적으로 P명보다 많은 사람이 기차에 탈 수 없습니다.

i번째 줄 j번째에 입력되는 C_ij는 i번 역에서 i+j번 역으로 이동하는 비용입니다.

i번째 줄 j번째에 입력되는 D_ij는 i번 역에서 i+j번 역으로 이동하기를 희망하는 사람의 수입니다.

i번째 줄 j번째에 입력되는 O_ij는 i번 역에서 i+j번 역으로 이동하는 공무원으로, 이들은 필수적으로 무조건 이동해야 하며 티켓의 비용을 받지 않습니다.

위의 규칙에 따라서 승객들을 선택적으로 이동시킬 때 벌어들일 수 있는 최대 티켓 비용의 합을 구하는 문제입니다.

 

승객들이 기차를 통해 이동하는 제한이 걸려있는 전형적인 Flow 문제인데, 최대 비용을 구하는 문제이기 때문에 MCMF 알고리즘을 사용해야 합니다.

 

 

 

우선 Sour와 Sink를 정해놓고 1번 노드부터 N번 노드까지를 순서대로 이은 뒤, P명의 승객을 제한시키기 위해 Sour에서 1번 노드로 가는 간선과 N번에서 Sink 노드로 가는 간선의 Capacity를 P명으로 제한합니다.

승객이 기차를 타지 않는 선택지도 당연히 두어야하므로, i번에서 i+1번으로 이동하는 간선은 INF의 capacity로 연결하며 비용은 0으로 설정합니다.

기차를 타는 경우에 대한 간선을 만들기 위해 a번 역에서 b번 역으로 이동한다고 가정하면 a번 노드에서 b번 노드로 D_ij의 capacity와 -C_ij의 비용을 가지는 간선을 만들어줍니다. (MCMF로 최댓값을 구해야하므로 음의 간선을 놓고 나온 결과값에 다시 마이너스 부호를 붙여 결과를 얻는 방식)

 

가장 문제가 되는 부분은 공무원들인데, 이들은 비용을 받지 않고 P명 중에서 일부 자리를 차지하기 때문에 처리가 까다롭습니다.

제가 선택한 방법은 이들을 -100만의 큰 비용으로 설정을 하여 flow를 흘렸을 때 공무원을 무조건 우선적으로 이동시키도록 하고, 얻어진 답의 마이너스 값에 다시 100만×공무원의 수를 빼서 답을 구하는 방식입니다.

그렇게 하면 계산 과정의 값을 손상시키지 않고 답을 온전하게 얻어낼 수 있게 됩니다.

 

 

#include <bits/stdc++.h>
#define MAX 20
#define INF 1000000000
using namespace std;

struct Edge {
    int Next, Capacity, Cost, Flow;
    Edge* Rev;
    Edge(int Next_, int Capacity_, int Cost_) : Next(Next_), Capacity(Capacity_), Cost(Cost_), Flow(0) {}
    int Remain() { return Capacity - Flow; }
    void AddFlow(int Amount) {
        Flow += Amount;
        Rev->Flow -= Amount;
    }
};
vector<Edge*> Line[MAX];

void AddLine(int From, int To, int Capacity, int Cost) {
    Edge* E = new Edge(To, Capacity, Cost);
    Edge* RevE = new Edge(From, 0, -Cost);
    E->Rev = RevE, RevE->Rev = E;
    Line[From].push_back(E), Line[To].push_back(RevE);
}

int MCMF(int Sour, int Sink) {
    int CostSum = 0;
    while(true) {
        Edge* Path[MAX];
        int Prev[MAX]; fill(Prev, Prev+MAX, -1);
        int Cost[MAX]; fill(Cost, Cost+MAX, INF); Cost[Sour] = 0;
        queue<int> Queue; Queue.push(Sour);
        bool inQueue[MAX] = {}; inQueue[Sour] = true;

        while(!Queue.empty()) {
            int Curr = Queue.front(); Queue.pop();
            inQueue[Curr] = false;
            for(int i=0; i<Line[Curr].size(); i++) {
                int Next = Line[Curr][i]->Next;
                if(Line[Curr][i]->Remain() > 0 && Cost[Curr] + Line[Curr][i]->Cost < Cost[Next]) {
                    Cost[Next] = Cost[Curr] + Line[Curr][i]->Cost;
                    Prev[Next] = Curr;
                    Path[Next] = Line[Curr][i];
                    if(!inQueue[Next]) Queue.push(Next), inQueue[Next] = true;
                }
            }
        }
        if(Prev[Sink] == -1) break;

        int Amount = INF;
        for(int i=Sink; i!=Sour; i=Prev[i])
            Amount = min(Amount, Path[i]->Remain());
        for(int i=Sink; i!=Sour; i=Prev[i]) {
            CostSum += Amount*Path[i]->Cost;
            Path[i]->AddFlow(Amount);
        }
    }
    return CostSum;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int T; cin >> T;
    while(T--) {
        for(int i=0; i<MAX; i++) vector<Edge*>().swap(Line[i]);
        int N, P, Capacity[MAX][MAX], SinCost[MAX][MAX];
        cin >> N >> P;
        int Sour = N+1, Sink = N+2;
        AddLine(Sour, 1, P, 0);
        AddLine(N, Sink, P, 0);
        for(int i=1; i<N; i++) AddLine(i, i+1, INF, 0);
        for(int i=1; i<N; i++)
            for(int j=1; i+j<=N; j++) cin >> SinCost[i][i+j];
        for(int i=1; i<N; i++)
            for(int j=1; i+j<=N; j++) {
                cin >> Capacity[i][i+j];
                AddLine(i, i+j, Capacity[i][i+j], -SinCost[i][i+j]);
            }
        int sumO = 0;
        for(int i=1; i<N; i++)
            for(int j=1; i+j<=N; j++) {
                int O; cin >> O; sumO += O;
                AddLine(i, i+j, O, -1000000);
            }
        cout << -MCMF(Sour, Sink)-1000000*sumO << "\n";
    }
}

 

풀이는 위와 같으며, 이 문제에서는 N이 아주 작기 때문에 MAX를 적당히 20 정도로만 설정해도 충분합니다.

 

 

 

제출하면 위와 같이 정답 처리를 받을 수 있으며, 채점 결과를 확인해보면 (4ms의 통과 시간이면) 굉장히 상위권의 등수를 기록할 수 있습니다.