1626 두 번째로 작은 스패닝 트리 문제와 유사하다.
https://lyzqm.blogspot.kr/2017/07/1626.html
그래프 $G$가 $m_{i}$의 간선들로 이루어져있을 때 각각의 $m_{i}$에 대해서 해당 간선이 존재하지 않을때
MST의 값을 구하는 문제이다.
처음에 떠오른 생각은 우선 MST를 만든후 $m_{i}$가 트리 간선인 경우 해당 간선을 지우고
트리간선이 아닌 다른간선으로 대체하는 방안을 떠올렸다.
($m_{i}$가 트리간선이 아닌경우는 MST값이 나올것이다.)
이 component를 연결하는 최소의 값을 지닌 회색 간선이 트리간선을 대체할 수 있을 것이다.
(검정색 - 트리간선, 회색 - 트리간선이 아닌 간선(일반간선으로 칭함))
문제는 어떻게 하느냐 인데 1626문제에서 처럼 LCA를 이용한다.
대신 일반 간선의 입장에서 생각해야한다.
이 간선은 {$u,v$}정점을 가리킬때 $u$에서 $v$로 가는 모든 MST 간선을 대체 할 수 있게 된다.
해당 일반간선이 MST간선을 대체할 수 있더라도 더 작은 일반 간선에 의해 대체 가능할 수 도
있기 때문에 작은 일반간선부터 대체 가능한 MST 간선을 정해놓아야 한다.
따라서 $m_{i}$가 {$u,v$}일 때 {$u, LCA$}, {$LCA, v$}의 아직 대체 되지 않은 MST간선을 구해서 갱신해주면 된다.
하지만 이 갱신작업을 depth를 한칸 한칸씩 내리며 찾는다면 TLE가 나온다.
따라서 중복되지 않도록 최적화를 시켜줘야 하는데 다음과 같은 방법을 사용하였다.
위와 같이 붉은 선은 이미 갱신되었고 $u$에서 $LCA$로 이동한다고 한다면
이미 갱신된 트리간선은 갈 필요가 없다.
그러므로 갱신될때마다 경로를 $LCA$로 변경시켜 주면 된다.
(추가적인 갱신조건은 코드를 참고)
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
int N, M;
int par[100001], rrank[100001], depth[100001];
int pr[100001];
int edge[200001];
ll ans[200001];
int pprev[100001][21];
bool isMSTedge[200001];
pair<ll, pair<int, pair<int, int>>> adj[200001]; //(d, index, u, v)
ll adj_copy[200001];
vector<pair<ll, pair<int, int>>> adj_mst[100001]; //u - (d, index, v)
pair<ll, pair<int,int>> adj_n_mst[200001]; //MST아닌 간선 (d, u, v)
void init() {
memset(depth, -1, sizeof depth);
for (int n = 0;n < M;n++) ans[n] = -1;
for (int n = 1;n <= N;n++)
par[n] = n, rrank[n] = 0;
}
int find(int x) {
if (x == par[x]) return x;
return par[x] = find(par[x]);
}
bool merge(int u, int v) {
u = find(u), v = find(v);
if (u == v) return false;
if (rrank[u] > rrank[v]) swap(u, v);
else if (rrank[u] == rrank[v]) rrank[v]++;
par[u] = v;
return true;
}
void dfs(int here) {
for (auto n : adj_mst[here]) {
int next = n.second.second;
if (depth[next] == -1) {
int idx = n.second.first;
depth[next] = depth[here] + 1;
pprev[next][0] = here;
pr[next] = here;
edge[next] = idx;
dfs(next);
}
}
}
void preprocess() {
for (int j = 1;j < 21;j++) {
for (int i = 1;i <= N;i++) {
pprev[i][j] = pprev[pprev[i][j - 1]][j - 1];
}
}
}
int getLCA(int u, int v) {
if (depth[u] < depth[v]) swap(u, v);
for (int i = 20;i >= 0;i--) {
if (depth[u] - depth[v] >= (1 << i))
u = pprev[u][i];
}
if (u == v) return u;
for (int i = 20;i >= 0;i--) {
if (pprev[u][i] != pprev[v][i])
u = pprev[u][i], v = pprev[v][i];
}
return pprev[u][0];
}
int main() {
scanf("%d%d", &N, &M);
init();
for (int m = 0;m < M;m++) {
int u, v, d;
scanf("%d%d%d", &u, &v, &d);
adj[m] = { (ll)d,{m,{u,v} } };
adj_copy[m] = (ll)d;
}
sort(adj, adj + M);
ll mst_val = 0;
int mst_cnt = 0; //
int n_mst_cnt = 0;
for (int m = 0;m < M;m++) {
ll d = adj[m].first;
int u = adj[m].second.second.first, v = adj[m].second.second.second;
if (merge(u, v) && mst_cnt < N - 1) { //서로다른 집합인 경우 - MST
int idx = adj[m].second.first;
isMSTedge[idx] = true;
adj_mst[u].push_back({ d, { idx, v } });
adj_mst[v].push_back({ d, { idx, u } });
mst_val += d;
++mst_cnt;
}
else { //MST아닌 간선
adj_n_mst[n_mst_cnt] = { d,{u,v} }, ++n_mst_cnt;
}
}
if (mst_cnt != N - 1) {
for (int m = 0;m < M;m++) printf("-1\n");
return 0;
}
depth[1] = 0;
dfs(1);
preprocess(); //2^K의 자식노드 전처리
int cnt = 0;
sort(adj_n_mst, adj_n_mst + n_mst_cnt);
for (int m = 0;m < n_mst_cnt;m++) { //MST 간선이 아닌 간선들
ll d = adj_n_mst[m].first;
int u = adj_n_mst[m].second.first, v = adj_n_mst[m].second.second;
int lca = getLCA(u, v);
if (lca != u) {
while (1) { // path(u, lca)
int idx = edge[u];
if (ans[idx] == -1) {
cnt++;
ans[idx] = mst_val + d - adj_copy[idx];
}
int tmp_u = u;
u = pr[u];
if (depth[lca] < pr[tmp_u])
pr[tmp_u] = lca;
if (depth[lca] >= depth[u]) break;
}
}
if (lca != v) {
while (1) { // path(v, lca)
int idx = edge[v];
if (ans[idx] == -1) {
cnt++;
ans[idx] = mst_val + d - adj_copy[idx];
}
int tmp_v = v;
v = pr[v];
if (depth[lca] < pr[tmp_v])
pr[tmp_v] = lca;
if (depth[lca] >= depth[v]) break;
}
}
if (cnt == mst_cnt) break;
}
for (int m = 0;m < M;m++) {
if (!isMSTedge[m]) printf("%lld\n", mst_val); //mst가 아닌 간선 - 변함없음
else printf("%lld\n", ans[m]);
}
return 0;
}
| cs |
댓글 없음:
댓글 쓰기