백준14510 Blazing New Trails

작성일 | In

문제 링크

  • http://icpc.me/14510

문제 출처

  • 2017 NAIPC E번

사용 알고리즘

  • Alien Trick
  • MST

시간복잡도

  • $O(M \log M \log X)$

풀이

special space와 nonspecial space를 잇는 간선을 빨간색 간선, 그렇지 않은 간선을 파란색 간선이라고 합시다.
w개의 빨간색 간선을 사용했을 때의 MST를 구하는 문제가 됩니다.

그냥 정답을 구하는 것은 힘들 것 같으니까 Alien’s Trick을 생각해볼 수 있습니다.
빨간색 개수 조건을 없애고, 파란색 간선을 사용하는 비용을 C만큼 증가시킨 다음에 MST를 구해봅시다. C가 커질수록 빨간색 간선을 많이 사용할 것이고, C가 작아질수록 빨간색 간선을 적게 사용할 것입니다. 그렇다면, 이분 탐색으로 빨간색 간선을 정확히 w개 사용하는 C를 찾으면 문제를 풀 수 있습니다.

그러한 C가 항상 존재한다는 것에 대한 증명은 여기에서 볼 수 있습니다.

이분 탐색에서 탐색할 C의 범위를 X라고 한다면, 크루스칼 알고리즘을 log X번 수행하기 때문에 $O(M \log M \log X)$에 풀 수 있습니다.

전체 코드

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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct Edge{
    int s, e, x, f;
    Edge() = default;
    Edge(int s, int e, int x, int f) : s(s), e(e), x(x), f(f) {}
    bool operator < (const Edge &t) const { return tie(x,f) < tie(t.x,t.f); }
};

struct UnionFind{
    int P[202020];
    UnionFind(){ clear(); }
    void clear(){ iota(P, P+202020, 0); }
    int find(int v){ return v == P[v] ? v : P[v] = find(P[v]); }
    bool merge(int u, int v){
        u = find(u); v = find(v);
        if(u == v) return false;
        P[u] = v; return true;
    }
};

int N, M, K, W, C[202020];
UnionFind UF;
vector<Edge> E;

pair<ll,ll> Solve(ll c){
    ll val = 0, cnt = 0;
    auto edges = E;
    for(auto &[s,e,x,f] : edges) if(f) x += c;
    sort(edges.begin(), edges.end());

    UF.clear();
    for(const auto &[s,e,x,f] : edges) if(UF.merge(s, e)) val += x, cnt += f;
    return {val, cnt};
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> M >> K >> W;
    for(int i=1,t; i<=K; i++) cin >> t, C[t] = 1;

    int comp = N;
    for(int i=1; i<=M; i++){
        int s, e, x; cin >> s >> e >> x;
        comp -= UF.merge(s, e);
        E.emplace_back(s, e, x, C[s] != C[e]);
    }
    if(comp > 1){ cout << -1; return 0; }

    ll l = -1e6, r = 1e6, res = -1;
    if(Solve(l).second < W || Solve(r).second > W){ cout << -1; return 0; }
    while(l <= r){
        ll m = l + r >> 1;
        auto [dp,cnt] = Solve(m);
        res = max(res, dp - W*m);
        if(cnt <= W) r = m - 1;
        else l = m + 1;
    }
    cout << res;
}