1626번: 두 번째로 작은 스패닝 트리
첫째 줄에 그래프의 정점의 수 V(1 ≤ V ≤ 50,000)와 간선의 수 E(1 ≤ E ≤ 200,000)가 들어온다. 둘째 줄부터 E+1번째 줄까지 한 간선으로 연결된 두 정점과 그 간선의 가중치가 주어진다. 가중치는 100,
www.acmicpc.net
생애 첫 다이아문제 AC라 기분이 좋군요 ㅎㅎ
boj 15481 그래프와 MST
www.acmicpc.net/problem/15481 15481번: 그래프와 MST 첫째 줄에 정점의 개수 N과 간선의 개수 M (2 ≤ N ≤ 200,000, N-1 ≤ M ≤ 200,000) 둘째 줄부터 M개의 줄에 간선의 정보 u, v, w가 주어진다. u와 v를..
emoney96.tistory.com
이 문제를 풀기 전에 그래프와 MST 문제를 풀어봐야합니다. (풀이가 비슷합니다.)
두 번째로 작은 스패닝 트리는 최소 스패닝 트리에서 하나의 간선만 바꿔주면 됩니다.
즉, 하나의 간선이 다릅니다.
1. 먼저 주어진 간선들로 첫 번째 mst를 구합니다.
2. 첫 번째 mst에 사용된 간선들로 인접 리스트를 만듭니다.
3. 인접 리스트의 depth를 구합니다.
4. 간선정보를 하나씩 가져와서 lca를 각각 구합니다.
5. mst - lca(u, v) + w의 최소를 구합니다.
여기까지는 그래프와 MST문제와 별다를게 없지만 이문제와의 차이점이 있습니다.
1. 두 번째 mst가 첫 번째 mst보다 커야함 -> 두 번째 mst를 구하지 못할 수 있음
2. 첫 번째 mst조차 구하지 못할 수 있음
위의 경우에는 -1을 출력해야합니다.
2번 경우를 확인할 때는 첫 번째 mst를 구할 때 고른 간선이 N - 1개인지 확인하는 것으로 예외처리 합니다.
1번 경우를 확인할 때는 lca로 u ~ v 경로의 간선을 구할 때
두개의 간선(가장 높은 가중치의 간선과 그 다음 높은 가중치의 간선)을 구합니다.
가장 높은 간선이 추가할 간선과 가중치가 같으면 1번조건에 걸리기 때문에 그 다음 높은 간선을 제거해야합니다.
마지막으로 ans가 최댓값이면 -1, 아니면 갱신된 값을 출력해줍니다.
정리하자면
1. 주어진 간선들로 첫 번째 mst를 구합니다.
2. 첫 번째 mst에 사용된 간선들로 인접 리스트를 만듭니다.
3. 인접 리스트의 depth를 구합니다.
4. lca(u, v)로 첫 번째, 두 번째 간선을 구합니다.
5. 구한 간선들이 w와 다를 경우에만 ans를 갱신합니다.
6. ans가 max값이면 -1, 아니면 갱신된 값을 출력합니다.
|
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
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
|
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#define MAX 50000
#define LOG 20
using namespace std;
typedef struct edge {
int u;
int v;
int w;
}edge;
vector<pair<int, int> > list[MAX + 1];
vector<edge> v;
pair<int, pair<int, int> > lcaParent[MAX + 1][LOG];
int mstParent[MAX + 1], depth[MAX + 1];
bool visit[MAX + 1];
int mst;
int N, M, cnt;
bool cmp(edge a, edge b) {
return a.w < b.w;
}
pair<int, int> f(pair<int, int> a, pair<int, int> b) {
vector<int> nv;
nv.push_back(a.first);
nv.push_back(a.second);
nv.push_back(b.first);
nv.push_back(b.second);
sort(nv.rbegin(), nv.rend());
nv.erase(unique(nv.begin(), nv.end()), nv.end());
if (nv.size() < 2) nv.push_back(-1);
return { nv[0], nv[1] };
}
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;
int w = list[v][i].second;
if (visit[next]) continue;
lcaParent[next][0] = { v,{w,-1} };
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, int 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 = v[i].u;
int y = v[i].v;
int w = v[i].w;
Union(x, y, w);
if (cnt == N - 1) break;
}
}
void init() {
for (int i = 1; i <= N; i++) {
mstParent[i] = i;
}
memset(lcaParent, -1, sizeof(lcaParent));
}
pair<int, int> lca(int x, int y) {
if (depth[x] > depth[y]) swap(x, y);
pair<int, int> ret = { -1,-1 };
for (int i = LOG - 1; i >= 0; i--) {
if (depth[y] - depth[x] >= (1 << i)) {
ret = f(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 = f(ret, lcaParent[x][i].second);
ret = f(ret, lcaParent[y][i].second);
x = lcaParent[x][i].first;
y = lcaParent[y][i].first;
}
}
ret = f(ret, lcaParent[x][0].second);
ret = f(ret, lcaParent[y][0].second);
return ret;
}
void func() {
if (cnt < N - 1) {
cout << "-1\n";
return;
}
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;
if (lcaParent[i][j].first == -1) continue;
lcaParent[i][j].second = f(lcaParent[i][j - 1].second, lcaParent[lcaParent[i][j - 1].first][j - 1].second);
}
}
long long ans = 2147483647;
for (int i = 0; i < M; i++) {
int x = v[i].u;
int y = v[i].v;
int w = v[i].w;
pair<int, int> sub = lca(x, y);
if (sub.first != w && sub.first != -1) ans = min(ans, (long long)(mst - sub.first + w));
else if (sub.second != w && sub.second != -1) ans = min(ans, (long long)(mst - sub.second + w));
}
if (ans >= 2147483647) cout << "-1\n";
else cout << ans << '\n';
}
void input() {
int x, y;
int w;
cin >> N >> M;
for (int i = 0; i < M; i++) {
cin >> x >> y >> w;
v.push_back({ x,y,w });
}
sort(v.begin(), v.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 6059 Pasture Walking (0) | 2021.06.16 |
|---|---|
| boj 3584 가장 가까운 공통 조상 (0) | 2021.06.16 |
| boj 15481 그래프와 MST (0) | 2021.04.01 |
| boj 15480 LCA와 쿼리 (0) | 2021.02.14 |
| boj 11438 LCA 2 (0) | 2021.02.11 |