백준19619 자매 도시

작성일 | In

문제 링크

  • http://icpc.me/19619

문제 출처

  • 2020 APIO 2번

사용 알고리즘

  • MST
  • HLD

시간복잡도

  • HLD + Segment Tree: $O(M \log M + Q \log^2 N)$
  • Sparse Table: $O(M \log M + Q \log N)$

풀이

MST는 다음과 같은 성질을 갖고 있습니다.

  • 경로 위에 있는 가중치의 최댓값을 최소화

이 문제에서 요구하는 쿼리와 MST의 성질이 잘 맞는 것 같으니 MST 위주로 풀이를 생각해봅시다.

두 자동차가 위치를 교환할 수 있는 경우에 그래프가 어떤 형태인지, 그리고 어떤 방식으로 이동하는지 알아봅시다.

  • degree가 3 이상인 정점 x가 존재
    • 첫 번째 차가 x까지 이동한 다음, 한 칸 더 가서 주차함
    • 두 번째 차가 x까지 이동한 다음, 도착 지점으로 이동
    • 주차한 상태였던 첫 번째 차가 다시 출발해서 도착 지점으로 이동
  • 사이클이 존재
    • 두 차 모두 사이클로 들어간 뒤, 사이클을 돌면서 위치를 교환

두 가지 경우에 모두 속하지 않는 그래프는 선형 그래프밖에 없습니다. 즉, 선형 그래프가 아니라면 항상 두 자동차가 위치를 교환할 수 있습니다.

두 자동차가 위치를 교환할 수 있는 상태를 나타내는 새로운 정점 $X$를 만듭시다. 두 자동차 $U, V$가 위치를 교환하는 비용은 max($U$에서 $X$로 이동하는 비용 + $V$에서 $X$로 이동하는 비용, $U$에서 $V$로 이동하는 비용)이 됩니다.
$X$를 포함해서 MST를 구축하면 Sparse Table이나 HLD+Segment Tree를 이용해서 문제를 풀 수 있습니다.

두 자동차가 위치를 교환할 수 있는 조건은 (1) degree가 3 이상인 정점 x에 도달함, (2) 사이클에 도달함, 총 2가지입니다.
원래 주어진 그래프에서 크루스칼 알고리즘을 이용해 MST를 만들어주면서

  1. 차수가 3 이상이 된 정점 $Y$에 대해 $X$와 $Y$를 잇는 간선을 추가해주고
  2. 어떤 간선이 잇는 두 정점 $Y_1, Y_2$가 이미 같은 컴포넌트에 속한 경우, $X$와 $Y_1$을 잇는 간선과 $X$와 $Y_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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include "swap.h"
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef long long ll;
typedef pair<ll, ll> p;

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

int par[101010];
int find(int v){ return v == par[v] ? v : par[v] = find(par[v]); }
int merge(int u, int v){ u = find(u); v = find(v); return u == v ? 0 : (par[u] = v, 1); }

const int sz = 1 << 17;
struct Seg{
    int tree[1 << 18];
    void update(int x, int v){
        x |= sz; tree[x] = v;
        while(x >>= 1) tree[x] = max(tree[x << 1], tree[x << 1 | 1]);
    }
    int query(int l, int r){
        l |= sz; r |= sz; int ret = 0;
        while(l <= r){
            if(l & 1) ret = max(ret, tree[l++]);
            if(~r & 1) ret = max(ret, tree[r--]);
            l >>= 1; r >>= 1;
        }
        return ret;
    }
};

struct HLD{
    vector<p> inp[101010]; vector<int> g[101010]; Seg seg;
    int in[101010], top[101010], dep[101010], sz[101010], par[101010], w[101010], pv;
    void dfs(int v, int b){
        for(auto i : inp[v]) if(i.x != b) g[v].push_back(i.x), w[i.x] = i.y, dep[i.x] = dep[v] + 1, par[i.x] = v, dfs(i.x, v);
    }
    void dfs1(int v){
        sz[v] = 1;
        for(auto &i : g[v]){
            dfs1(i); sz[v] += sz[i];
            if(sz[i] > sz[g[v][0]]) swap(i, g[v][0]);
        }
    }
    void dfs2(int v){
        in[v] = ++pv;
        for(auto i : g[v]) top[i] = i == g[v][0] ? top[v] : i, dfs2(i);
    }
    void init(int n){
        dfs(0, -1); dfs1(0); dfs2(0);
        for(int i=0; i<n; i++) seg.update(in[i], w[i]);
    }
    int query(int u, int v){
        int ret = 0;
        for(; top[u] != top[v]; u=par[top[u]]){
            if(dep[top[u]] < dep[top[v]]) swap(u, v);
            ret = max(ret, seg.query(in[top[u]], in[u]));
        }
        if(dep[u] > dep[v]) swap(u, v);
        return max(ret, seg.query(in[u]+1, in[v]));
    }
    void addEdge(int s, int e, int x){ inp[s].emplace_back(e, x); inp[e].emplace_back(s, x); }
} t1, t2;

int n, m, deg[101010], flag;
vector<Edge> edge;
vector<int> g[101010];

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
    n = N; m = M; edge.resize(m);
    for(int i=0; i<m; i++){
        edge[i].s = U[i]; edge[i].e = V[i]; edge[i].x = W[i];
        g[edge[i].s].push_back(edge[i].e); g[edge[i].e].push_back(edge[i].s);
    }
    sort(all(edge)); iota(par, par+101010, 0);
    for(auto i : edge) if(merge(i.s, i.e)) t1.addEdge(i.s, i.e, i.x);
    iota(par, par+101010, 0);
    for(auto i : edge){
        if(merge(i.s, i.e)) t2.addEdge(i.s, i.e, i.x);
        else{
            if(merge(i.s, n)) t2.addEdge(i.s, n, i.x);
            if(merge(i.e, n)) t2.addEdge(i.e, n, i.x);
        }
        if(++deg[i.s] == 3 && merge(i.s, n)) t2.addEdge(i.s, n, i.x), flag = 1;
        if(++deg[i.e] == 3 && merge(i.e, n)) t2.addEdge(i.e, n, i.x), flag = 1;
    }
    if(n <= m) flag = 1;
    t1.init(n); t2.init(n+1);
}

int getMinimumFuelCapacity(int a, int b){
    if(!flag) return -1;
    return max({t1.query(a, b), t2.query(a, b), t2.query(a, n), t2.query(b, n)});
}