15481번: 그래프와 MST
첫째 줄에 정점의 개수 N과 간선의 개수 M (2 ≤ N ≤ 200,000, N-1 ≤ M ≤ 200,000) 둘째 줄부터 M개의 줄에 간선의 정보 u, v, w가 주어진다. u와 v를 연결하는 간선의 가중치가 w라는 뜻이다. (1 ≤ u, v ≤
www.acmicpc.net
M개의 간선 정보가 들어오는데 i번째 간선을 포함한 MST를 출력하는 문제입니다.
우선 전체 MST를 구해줍니다.
그 다음 i번째 간선을 포함해주고 그 간선에 연결된 정점들의 경로에 있는 MST 간선을 하나 제거해야합니다.
이 경로를 순회해야 하기때문에 이를 LCA로 구합니다.
여기서 LCA를 구하기 전에 각 정점의 높이를 구해야하는데 인접 리스트를 MST 간선들만 가지고 구해줍니다.
그럼 u v 경로의 최대 간선을 구할 수 있습니다.
답은 mst - lca(u, v) + w을 출력해주시면 되고, 입력이 들어온 순서대로 출력해야하니 인덱스를 유지해야합니다.
정리하자면
1. 먼저 주어진 간선들로 MST를 구합니다.
2. MST에 사용된 간선들로 인접 리스트를 만들어줍니다.
3. 인접리스트의 depth를 구합니다.
4. 입력(간선 정보)이 들어왔던 순서대로 lca를 구해줍니다.
5. mst - lca(u, v) + w을 출력합니다.
|
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
133
134
135
136
137
138
139
140
141
|
#include <iostream>
#include <vector>
#include <algorithm>
#define MAX 200000
#define LOG 20
using namespace std;
typedef long long ll;
typedef struct edge {
int u;
int v;
ll w;
}edge;
vector<pair<int, ll> > list[MAX + 1];
vector<edge> v, nv;
pair<int, ll> lcaParent[MAX + 1][LOG];
int mstParent[MAX + 1], depth[MAX + 1];
bool visit[MAX + 1];
ll mst;
int N, M, cnt;
bool cmp(edge a, edge b) {
return a.w < b.w;
}
void dfs(int v, int d) {
depth[v] = d;
visit[v] = true;
for (int i = 0; i < list[v].size(); i++) {
int next = list[v][i].first;
ll w = list[v][i].second;
if (visit[next]) continue;
lcaParent[next][0] = { v,w };
dfs(next, d + 1);
}
}
int find(int v) {
if (mstParent[v] == v) return v;
return mstParent[v] = find(mstParent[v]);
}
void Union(int x, int y, ll w) {
int a = find(x);
int b = find(y);
if (a == b) return;
list[x].push_back({ y,w });
list[y].push_back({ x,w });
mstParent[b] = a;
mst += w;
cnt++;
}
void makeMst() {
for (int i = 0; i < M; i++) {
int x = nv[i].u;
int y = nv[i].v;
ll w = nv[i].w;
Union(x, y, w);
if (cnt == N - 1) break;
}
}
void init() {
for (int i = 1; i <= N; i++) {
mstParent[i] = i;
}
}
ll lca(int x, int y) {
if (depth[x] > depth[y]) swap(x, y);
ll ret = 0;
for (int i = LOG - 1; i >= 0; i--) {
if (depth[y] - depth[x] >= (1 << i)) {
ret = max(ret, lcaParent[y][i].second);
y = lcaParent[y][i].first;
}
}
if (x == y) return ret;
for (int i = LOG - 1; i >= 0; i--) {
if (lcaParent[x][i].first == 0) continue;
if (lcaParent[x][i].first != lcaParent[y][i].first) {
ret = max(ret, max(lcaParent[x][i].second, lcaParent[y][i].second));
x = lcaParent[x][i].first;
y = lcaParent[y][i].first;
}
}
return max(ret, max(lcaParent[x][0].second, lcaParent[y][0].second));
}
void func() {
dfs(1, 1);
for (int j = 1; j < LOG; j++) {
for (int i = 1; i <= N; i++) {
lcaParent[i][j].first = lcaParent[lcaParent[i][j - 1].first][j - 1].first;
lcaParent[i][j].second = max(lcaParent[i][j - 1].second, lcaParent[lcaParent[i][j - 1].first][j - 1].second);
}
}
for (int i = 0; i < M; i++) {
int x = v[i].u;
int y = v[i].v;
ll w = v[i].w;
ll sub = lca(x, y);
cout << mst - sub + w << '\n';
}
}
void input() {
int x, y;
ll w;
cin >> N >> M;
for (int i = 0; i < M; i++) {
cin >> x >> y >> w;
v.push_back({ x,y,w });
}
nv = v;
sort(nv.begin(), nv.end(), cmp);
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
input();
init();
makeMst();
func();
return 0;
}
|
cs |
'algorithm > LCA' 카테고리의 다른 글
| boj 3584 가장 가까운 공통 조상 (0) | 2021.06.16 |
|---|---|
| boj 1626 두 번째로 작은 스패닝 트리 (0) | 2021.04.02 |
| boj 15480 LCA와 쿼리 (0) | 2021.02.14 |
| boj 11438 LCA 2 (0) | 2021.02.11 |
| boj 11437 LCA (0) | 2021.02.11 |