백준10169 안전한 비상연락망

작성일 | In

문제 링크

  • http://icpc.me/10169

문제 출처

  • 2014 KOI 고등부 4번

사용 알고리즘

  • HLD
  • MST
  • 세그 레이지

시간복잡도

  • $O(M \log M + M \log^2 N)$

풀이

일단 MST를 구합시다.

$i$번째 간선이 MST에 속하지 않는다면, $i$번째 정답은 MST의 비용과 동일합니다. MST에 속한 간선이 제거될 때 정답이 어떻게 변하는지 빠르게 찾는 것이 문제의 핵심입니다.
MST에 속한 어떤 간선 $(u, v)$를 제거하면 트리는 ($u$가 속한 컴포넌트)와 ($v$가 속한 컴포넌트)로 나뉘게 됩니다. 쪼개진 두 컴포넌트를 다시 이어줄 대체 간선, 그 중에서도 최소 비용 대체 간선을 찾는 문제로 바뀌게 됩니다.

MST에 속하지 않은 간선 $e = (a, b)$가 MST에 추가된다면, $a - (Tree\ Path) - b - e - a$ 사이클이 만들어집니다. 또한 $(Tree\ Path)$에 속한 간선 하나가 제거되면 다시 Spanning Tree가 됩니다.
그러므로 MST에 속하지 않은 간선 $(a, b)$은, MST 상의 경로 $(a, b)$ 위에 있는 간선의 대체 간선으로 사용할 수 있다는 것을 알 수 있습니다.

이제 문제가 매우 쉬워졌습니다.
MST에 속하지 않은 간선 $e = (a, b, weight)$에 대해, MST 상의 경로 $(a, b)$에 속한 모든 간선에 $weight$라는 태그를 달아줍시다. 그러면 MST에 속한 간선 $(u, v)$의 대체 간선을 찾는 것은 간선 $(u, v)$에 붙은 태그의 최솟값을 구하면 됩니다.
이 작업은 HLD와 Segment Tree + Lazy Propagation을 이용해 $O(M \log^2 N)$에 처리할 수 있습니다.

전체 코드

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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
/******************************
Author: jhnah917(Justice_Hui)
g++ -std=c++17 -DLOCAL
******************************/

#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())
#define IDX(v, x) lower_bound(all(v), x) - v.begin()
using namespace std;

using uint = unsigned;
using ll = long long;
using ull = unsigned long long;
const ll INF = 0x3f3f3f3f3f3f3f3f;

namespace library{
    template<typename cost_t> struct Edge{
        int s, e; cost_t x; int id;
        bool operator < (const Edge &t) const { return x < t.x; }
    };
    template<size_t _Sz> struct UnionFind{
        int P[_Sz];
        UnionFind(){ iota(P, P+_Sz, 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;
        }
    };
    template<typename tree_t, size_t _Sz> struct SegmentTree{
        tree_t T[_Sz << 1], L[_Sz << 1];
        SegmentTree(){
            memset(T, 0x3f, sizeof T);
            memset(L, 0x3f, sizeof L);
        }
        void Push(int node, int s, int e){
            T[node] = min(T[node], L[node]);
            if(s != e) for(const int c : {node<<1, node<<1|1}) L[c] = min(L[c], L[node]);
        }
        void Update(int l, int r, tree_t v, int node=1, int s=0, int e=_Sz-1){
            Push(node, s, e);
            if(r < s || e < l) return;
            if(l <= s && e <= r){ L[node] = v; Push(node, s, e); return; }
            int m = s + e >> 1;
            Update(l, r, v, node<<1, s, m);
            Update(l, r, v, node<<1|1, m+1, e);
            T[node] = min(T[node<<1], T[node<<1|1]);
        }
        tree_t Query(int l, int r, int node=1, int s=0, int e=_Sz-1){
            Push(node, s, e);
            if(r < s || e < l) return INF;
            if(l <= s && e <= r) return T[node];
            int m = s + e >> 1;
            return min(Query(l, r, node<<1, s, m), Query(l, r, node<<1|1, m+1, e));
        }
    };
}

namespace HLD{
    library::SegmentTree< ll, 1<<17 > Seg;
    vector<int> Input[101010], G[101010];
    int dep[101010], par[101010], sz[101010], top[101010], in[101010], pv;
    void AddEdge(int s, int e){ Input[s].push_back(e); Input[e].push_back(s); }
    void DFS(int v, int b){
        for(const auto &i : Input[v]){
            if(i == b) continue;
            par[i] = v; dep[i] = dep[v] + 1;
            DFS(i, v); G[v].push_back(i);
        }
    }
    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(const auto &i : G[v]) top[i] = i == G[v][0] ? top[v] : i, DFS2(i);
    }
    void Build(){ DFS(1, -1); DFS1(1); DFS2(top[1]=1); }
    void Update(int u, int v, ll color){
        for(; top[u] != top[v]; u=par[top[u]]){
            if(dep[top[u]] < dep[top[v]]) swap(u, v);
            Seg.Update(in[top[u]], in[u], color, 1, 1, pv);
        }
        if(in[u] > in[v]) swap(u, v);
        Seg.Update(in[u]+1, in[v], color, 1, 1, pv);
    }
    ll Query(int u, int v){
        ll ret = INF;
        for(; top[u] != top[v]; u=par[top[u]]){
            if(dep[top[u]] < dep[top[v]]) swap(u, v);
            ret = min(ret, Seg.Query(in[top[u]], in[u], 1, 1, pv));
        }
        if(in[u] > in[v]) swap(u, v);
        ret = min(ret, Seg.Query(in[u]+1, in[v], 1, 1, pv));
        return ret;
    }
}

int N, M, pv;
ll MST, R[303030];
vector<library::Edge<ll>> edge, mst, no;
library::UnionFind<101010> uf;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> M; edge.resize(M);
    for(auto &i : edge) cin >> i.s >> i.e >> i.x, i.id = ++pv;
    sort(all(edge));
    for(const auto &i : edge){
        if(uf.Merge(i.s, i.e)) mst.push_back(i), MST += i.x;
        else no.push_back(i);
    }
    if(mst.size() != N-1){ while(M--) cout << "-1\n"; return 0; }

    for(const auto &i : mst) HLD::AddEdge(i.s, i.e);
    HLD::Build();
    for(const auto &i : no) HLD::Update(i.s, i.e, i.x), R[i.id] = MST;
    for(const auto &i : mst){
        auto nxt = HLD::Query(i.s, i.e);
        if(nxt == INF) R[i.id] = -1;
        else R[i.id] = MST - i.x + nxt;
    }
    for(int i=1; i<=M; i++) cout << R[i] << "\n";
}