백준 1150번: 백업 [C++]

작성일 | In
다이아몬드 IV 다이아몬드 IV

문제

백업

풀이

인접하지 않은 두 회사를 케이블로 잇는 것은 손해라는 것을 자명하게 알 수 있습니다.

따라서 홀수번째 회사에서 짝수번째 회사로 가는 용량 1짜리의 간선을 잇고 최소 비용 최대 유량 알고리즘으로 해결할 수 있습니다.

다만 회사의 수가 너무 크므로 최적화가 필요합니다.

음의 유량 아이디어는 보낸 유량을 회수하고 다른 곳으로 보내는 아이디어입니다. 이 아이디어를 이용해서 그리디 알고리즘으로 해결할 수 있습니다.

먼저 우선순위 큐를 만들고 큐에 모든 간선 $(i, i + 1)$을 넣습니다. 큐에 담긴 간선 $(i, j)$의 가중치는 회사 $i$와 $j$를 선택하기 위한 비용이라고 생각하면 됩니다.

큐에서 가중치가 가장 작은 간선 $(i, i + 1)$을 꺼내고 답에 가중치를 더합니다. $i$번째 회사와 $i + 1$번째 회사는 더 이상 다른 회사와 이어질 수 없으므로 두 회사와 이어진 간선을 우선순위 큐에서 제거해야 합니다.

간선 $(i - 1, i)$와 $(i + 1, i + 2)$를 큐에서 실시간으로 제거하는 대신 $i$와 $i + 1$가 선택되었는지 기록한 다음 나중에 해당되는 간선을 큐에서 뽑았을 경우 continue하는 방식으로 구현하면 됩니다.

$(i, i + 1)$ 대신 다른 간선을 잇는 것이 이득인 경우를 고려하기 위해서 $(i - 1, i)$와 $(i + 1, i + 2)$의 가중치를 더한 값에 $(i, i + 1)$의 가중치를 뺀 간선 $(i - 1, i + 2)$를 큐에 새로 넣어줍니다.

두 간선 $(i - 1, i)$와 $(i + 1, i + 2)$ 중 하나만 사용하는 경우는 가중치가 가장 작은 것 부터 고른다는 알고리즘에 의해서 둘 모두를 고르는 것보다 손해임을 알 수 있습니다.

이때 큐에 새로 넣은 간선 $(i - 1, i + 2)$를 또 회수하고 다른 간선으로 잇는 게 이득인 경우도 생길 수 있습니다. 따라서 간선을 큐에서 꺼낼 때 마다 회사의 왼쪽, 오른쪽에 아직 점유되지 않은 가장 가까운 회사의 번호와 그 회사를 고르기 위한 비용을 기록해 주어야 합니다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <bits/stdc++.h>
#ifndef ONLINE_JUDGE
#define ASSERT(x) assert(x)
#else
#define ASSERT(_) ((void)0)
#endif
using namespace std;

template <typename T>
using MinHeap = priority_queue<T, vector<T>, greater<T>>;

int s[101010], l[101010], r[101010], lDist[101010], rDist[101010];
bool used[101010];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;

    MinHeap<tuple<int, int, int>> pq;

    cin >> s[0];
    r[0] = 1;
    for (int i = 1; i < n; i++) {
        cin >> s[i];

        l[i] = i - 1;
        r[i] = i + 1;
        lDist[i] = rDist[i - 1] = s[i] - s[i - 1];

        pq.emplace(lDist[i], i - 1, i);
    }

    int answer = 0;
    int count = 0;
    while (count < k) {
        auto [dist, i, j] = pq.top();
        pq.pop();

        if (used[i] or used[j])
            continue;

        answer += dist;
        count++;

        used[i] = used[j] = true;

        if (i == 0 or j == n - 1)
            continue;

        r[l[i]] = r[j];
        rDist[l[i]] += rDist[j] - dist;

        l[r[j]] = l[i];
        lDist[r[j]] += lDist[i] - dist;

        pq.emplace(lDist[i] + rDist[j] - dist, l[i], r[j]);
    }

    cout << answer;

    return 0;
}

백준 1150번: 백업 [C++]