BOJ 10169 - 안전한 비상연락망

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;  
      }  
   }  
}