BOJ 10169 - 안전한 비상연락망
Idea 1 - 내 풀이
이러한 문제를 이전에 풀어본 기억이 있다.
그래프 $G$의 MST를 구성한다.
MST에서 특정 간선이 끊겼을 때, MST에 포함되지 않은 간선들 중 하나를 새롭게 이어주고 새로운 MST의 비용을 구해야 한다.
따라서 원래 MST의 비용이 $C$라면,
$C_{new}=C-W_{removed}+W_{new}$ 이다.
$W_{removed}$는 이미 정해져 있으므로 $W_{new}$를 최소화 하는것이 관건이다.
간선 $E_{removed}$ 가 잇고 있는 정점 $u, v$ 를 고려할 때 ,결국 $\overline{uv}$ 를 다시 이어주게 만드는 MST에 포함되지 않았던 간선 중 가장 $W$가 작은 간선을 하나 고르면 된다는 뜻이다.
그런데, MST에 포함되지 않은 간선만 써서 만든 그래프가 트리라는 것이 보장이 되지 않으므로, 조금 특별하게 전처리를 해두어야 한다.
어떤 MST에 포함되지 않는 간선 $(u, v, w)$ 를 잇는다는 것은 MST에 있는 트리에서 $u \longleftrightarrow v$ 경로에 있는 모든 간선 중 하나를 없애도 이 간선으로 대체할 수 있다는 의미이다.
따라서 그 경로를 HLD와 Lazy Propagation Segment Tree를 이용해서 Min 연산을 구간 연산으로 업데이트 해준다.
이건 가장 느리고 쉬운 풀이이다. 비슷한 아이디어로 푸는건 맞지만, 더 빠르고 간단한 자료구조만 사용해서도 가능하다.
그러면 이제 각 간선을 보면서 이 간선이 MST에 포함되지 않았으면 정답은 원래 MST의 가중치 합이고,
MST에 포함되는 간선이면, MST 가중치 합에서 원래 간선의 가중치 W_{removed}를 빼고 $u, v$ 사이에 있는 가장 작게 업데이트 된 간선의 가중치를 더해준 것이 정답이다.
간선이 이어져있지 않으면 그 어떤 MST에 포함되지 않는 간선도 이 경로에 업데이트를 쳐주지 못했을 것이므로 그 경로에서의 Min 값이 $\infty$ 로 나오게 설정해두면 -1을 출력해주어야 할 조건도 처리할 수 있다.
int inf = 1e9 + 5;
struct DSU {
vector<int> p;
DSU(int n) : p(n, -1) {}
int gp(int n) {
if (p[n] < 0) return n;
return p[n] = gp(p[n]);
}
void merge(int a, int b, int to_b = 0) {
a = gp(a), b = gp(b);
if (a == b) return;
if (!to_b && size(a) > size(b)) swap(a, b);
p[b] += p[a];
p[a] = b;
}
bool is_merged(int a, int b) { return gp(a) == gp(b); }
int size(int n) { return -p[gp(n)]; }
};
struct LazySegTree {
int N;
vi tree, lazy;
LazySegTree(int N) : N(N) {
int size = 1 << int(ceil(log2(N)) + 1);
tree = vi(size, inf);
lazy = vi(size, inf);
}
void propagate(int n, int nl, int nr) {
if (lazy[n] != inf) {
tree[n] = min(tree[n], lazy[n]);
if (nl != nr) {
lazy[n * 2] = min(lazy[n * 2], lazy[n]);
lazy[n * 2 + 1] = min(lazy[n * 2 + 1], lazy[n]);
}
lazy[n] = inf;
}
}
void update(int n, int nl, int nr, int l, int r, int v) {
propagate(n, nl, nr);
if (nl > r || nr < l) return;
if (nl >= l && nr <= r) {
lazy[n] = min(lazy[n], v);
propagate(n, nl, nr);
return;
}
int m = nl + nr >> 1;
update(n * 2, nl, m, l, r, v);
update(n * 2 + 1, m + 1, nr, l, r, v);
tree[n] = min(tree[n * 2], tree[n * 2 + 1]);
}
int query(int n, int nl, int nr, int l, int r) {
propagate(n, nl, nr);
if (nl > r || nr < l) return inf;
if (nl >= l && nr <= r) return tree[n];
int m = nl + nr >> 1;
return min(query(n * 2, nl, m, l, r), query(n * 2 + 1, m + 1, nr, l, r));
}
};
struct E {
int to, cost;
};
struct HLD {
int N, dfsn = 0;
vi par, depth, head, in, sub;
LazySegTree seg;
vector<vector<E>> edges;
HLD(int N) : N(N), seg(LazySegTree(N)), edges(N) {
par = vi(N);
depth = vi(N);
head = vi(N);
in = vi(N);
sub = vi(N);
};
void add_edge(int u, int v, int w) {
edges[u].pb({v, w});
edges[v].pb({u, w});
};
void init() {
dfs1(0, -1);
dfs2(0);
}
void dfs1(int i, int p) {
sub[i] = 1;
par[i] = p;
for (int j = 0; j < sz(edges[i]); j++) {
auto &e = edges[i][j];
if (e.to == p) continue;
depth[e.to] = depth[i] + 1;
dfs1(e.to, i);
if (sub[e.to] > sub[edges[i][0].to] || edges[i][0].to == p) swap(edges[i][0], edges[i][j]);
sub[i] += sub[e.to];
}
}
void dfs2(int i) {
in[i] = dfsn++;
for (int j = 0; j < sz(edges[i]); j++) {
auto &e = edges[i][j];
if (e.to == par[i]) continue;
head[e.to] = j == 0 ? head[i] : e.to;
dfs2(e.to);
}
}
void update(int u, int v, int w) {
for (; head[u] ^ head[v]; u = par[head[u]]) {
if (depth[head[u]] < depth[head[v]]) swap(u, v);
seg.update(1, 0, N - 1, in[head[u]], in[u], w);
}
if (depth[u] > depth[v]) swap(u, v);
seg.update(1, 0, N - 1, in[u] + 1, in[v], w);
}
int query_min(int u, int v) {
int ret = inf;
for (; head[u] ^ head[v]; u = par[head[u]]) {
if (depth[head[u]] < depth[head[v]]) swap(u, v);
ret = min(ret, seg.query(1, 0, N - 1, in[head[u]], in[u]));
}
if (depth[u] > depth[v]) swap(u, v);
ret = min(ret, seg.query(1, 0, N - 1, in[u] + 1, in[v]));
return ret;
}
};
void solve() {
struct stat st;
fstat(0, &st);
char *p = (char *) mmap(0, st.st_size, PROT_READ, MAP_SHARED, 0, 0);
auto readInt = [&]() {
int ret = 0;
for (char c = *p++; c & 16; ret = 10 * ret + (c & 15), c = *p++);
return ret;
};
int N = readInt(), M = readInt(), u, v, w;
vector<array<int, 3>> edges;
vi included(M), idx(M);
DSU dsu(N);
for (int i = 0; i < M; i++) {
u = readInt() - 1, v = readInt() - 1, w = readInt();
edges.pb({u, v, w});
}
iota(all(idx), 0);
sort(all(idx), [&](int i, int j) { return edges[i][2] < edges[j][2]; });
ll mst_sum = 0;
HLD hld(N);
for (int i = 0; i < M; i++) {
const auto&[u, v, w] = edges[idx[i]];
if (dsu.is_merged(u, v)) continue;
dsu.merge(u, v);
mst_sum += w;
included[idx[i]] = 1;
hld.add_edge(u, v, 0);
}
hld.init();
for (int i = 0; i < M; i++) {
const auto&[u, v, w] = edges[i];
if (!included[i]) {
hld.update(u, v, w);
}
}
for (int i = 0; i < M; i++) {
const auto&[u, v, w] = edges[i];
if (!included[i]) {
cout << mst_sum << endl;
} else {
int alternate = hld.query_min(u, v);
if (alternate >= inf) cout << -1 << endl;
else cout << (mst_sum - w + alternate) << endl;
}
}
}
Comments