백준15481 그래프와 MST

작성일 | In

문제 링크

  • http://icpc.me/15481

풀이

일단 주어진 그래프에서 MST를 구하는 것은 크루스칼 알고리즘을 이용해 O(E log E)만에 할 수 있습니다.

크루스칼 알고리즘은 Union-Find 구조를 이용합니다. (u, v)를 잇는 간선이 MST에 추가된다면 u가 있는 집합과 v가 있는 집합을 union해줍니다.
반대로, (u, v)를 잇는 간선이 제거된다면 두 집합이 분리가 되겠죠.

(u, v)를 포함하는 MST를 구하는 것은, 주어진 그래프의 MST에서 (u, v)를 잇는 경로 중 가장 비용이 큰 간선을 제거해준 다음에 (u, v)간선을 넣어주면 됩니다.
이 작업은 LCA와 Sparse Table을 이용해 처리해줄 수 있습니다.

전체 코드

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
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

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

int chk[202020];
int dp[22][202020];
int dst[22][202020];
int dep[202020];

int par[202020];

int find(int v){
    return v == par[v] ? v : par[v] = find(par[v]);
}

bool merge(int u, int v){
    u = find(u), v = find(v);
    if(u == v) return 0;
    par[u] = v;
    return 1;
}

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

vector<Edge> edge;
vector<p> g[202020];

ll mst(){
    vector<Edge> v = edge;
    sort(v.begin(), v.end());
    for(int i=0; i<202020; i++) par[i] = i;
    ll ret = 0;
    for(auto i : v){
        int s = i.s, e = i.e, x = i.x;
        if(merge(s, e)){
            ret += x;
            g[s].push_back({e, x});
            g[e].push_back({s, x});
        }
    }
    return ret;
}

void dfs(int now, int prv = -1){
    for(auto i : g[now]){
        int nxt = i.x, cst = i.y;
        if(prv == nxt) continue;
        dp[0][nxt] = now;
        dep[nxt] = dep[now] + 1;
        dst[0][nxt] = cst;
        dfs(nxt, now);
    }
}

int lca(int u, int v){
    if(dep[u] < dep[v]) swap(u, v);
    int diff = dep[u] - dep[v];
    for(int i=0; diff; i++){
        if(diff & 1) u = dp[i][u];
        diff >>= 1;
    }
    if(u == v) return u;
    for(int i=21; i>=0; i--){
        if(dp[i][u] != dp[i][v]) u = dp[i][u], v = dp[i][v];
    }
    return dp[0][u];
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n, m; cin >> n >> m;
    for(int i=0; i<m; i++){
        int s, e, x; cin >> s >> e >> x;
        edge.push_back({s, e, x});
    }
    ll ret = mst();
    dfs(1, -1);
    for(int j=1; j<22; j++){
        for(int i=1; i<=n; i++){
            dp[j][i] = dp[j-1][dp[j-1][i]];
            dst[j][i] = max(dst[j-1][i], dst[j-1][dp[j-1][i]]);
        }
    }

    for(auto i : edge){
        int s = i.s, e = i.e, x = i.x; int l = lca(s, e);
        ll ans = ret;
        int mx = -1;
        int diff = dep[s] - dep[l];
        for(int j=0; diff; j++){
            if(diff & 1) mx = max(mx, dst[j][s]), s = dp[j][s];
            diff >>= 1;
        }
        diff = dep[e] - dep[l];
        for(int j=0; diff; j++){
            if(diff & 1) mx = max(mx, dst[j][e]), e = dp[j][e];
            diff >>= 1;
        }
        cout << ans - mx + x << "\n";
    }
}