Minimum spanning tree for each edge（倍增LCA）

https://vjudge.net/contest/320992#problem/J

暑期训练的题。

题意：给你一个n个点，m条边的无向图。对于每一条边，求包括该边的最小生成树。

思路：首先想到求一次整图的mst后，对每条边(u,v)，如果该边在整图的最小生成树上，答案就是mst，否则，加入的边(u,v)会使原来的最小生成树成环，可以通过lca确定该环，那么只要求出u到lca(u,v)路径上的最大边权和v到lca(u,v)路径上的最大边权中的最大值mx，mst-mx+w[u.v]就是答案。其中gx[u][i]表示节点u到其第2^i个祖先路径上的最大边权。

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 const int INF = 0x3f3f3f3f;
  4 const int N = 2e5 + 10;
  5 const int DEG = 20;
  6 typedef long long ll;
  7 struct edge {
  8     int v, w, next;
  9     edge() {}
 10     edge(int v, int w, int next) : v(v), w(w), next(next){}
 11 }e[N << 1];
 12 
 13 int head[N], tot;
 14 int fa[N][DEG], deg[N];
 15 int gx[N][DEG];
 16 void init() {
 17     memset(head, -1, sizeof head);
 18     tot = 0;
 19 }
 20 void addedge(int u, int v, int w) {
 21     e[tot] = edge(v, w, head[u]);
 22     head[u] = tot++;
 23 }
 24 void BFS(int root) {
 25     queue<int> que;
 26     deg[root] = 0;
 27     fa[root][0] = root;
 28     gx[root][0] = 0;
 29     que.push(root);
 30     while(!que.empty()) {
 31         int tmp = que.front();
 32         que.pop();
 33         for(int i = 1; i < DEG; ++i) {
 34             fa[tmp][i] = fa[ fa[tmp][i - 1] ][i - 1];
 35             gx[tmp][i] = max(gx[tmp][i - 1], gx[ fa[tmp][i - 1] ][i - 1]);
 36           // printf("[%d %d] ", tmp, gx[tmp][i]);
 37         }
 38        // puts("");
 39         for(int i = head[tmp]; ~i; i = e[i].next) {
 40             int v = e[i].v;
 41             int w = e[i].w;
 42             if(v == fa[tmp][0]) continue;
 43             deg[v] = deg[tmp] + 1;
 44             fa[v][0] = tmp;
 45             gx[v][0] = w;
 46             que.push(v);
 47         }
 48     }
 49 }
 50 int Mu, Mv;
 51 ll LCA(int u, int v) {
 52     Mu = Mv = -1;
 53     if(deg[u] > deg[v]) swap(u, v);
 54     int hu = deg[u], hv = deg[v];
 55     int tu = u, tv = v;
 56     for(int det = hv - hu, i = 0; det; det >>= 1, ++i)
 57         if(det & 1) { Mv = max(Mv, gx[tv][i]); tv = fa[tv][i];  }
 58     if(tu == tv) return Mv;
 59     for(int i = DEG - 1; i >= 0; --i) {
 60         if(fa[tu][i] == fa[tv][i]) continue;
 61         Mu = max(Mu, gx[tu][i]);
 62         Mv = max(Mv, gx[tv][i]);
 63         tu = fa[tu][i];
 64         tv = fa[tv][i];
 65 
 66 
 67     }
 68     return max(max(Mu, gx[tu][0]), max(Mv, gx[tv][0]));
 69 }
 70 
 71 int U[N], V[N], w[N], r[N], f[N];
 72 int find(int x) { return f[x] == x ? x : f[x] = find(f[x]); }
 73 bool cmp(int a, int b) { return w[a] < w[b]; }
 74 ll MST;
 75 int n, m;
 76 void mst() {
 77 
 78     scanf("%d%d", &n, &m);
 79     for(int i = 1; i <= m; ++i) {
 80         scanf("%d%d%d", &U[i], &V[i], &w[i]);
 81         r[i] = i;
 82         f[i] = i;
 83     }
 84     sort(r + 1, r + m + 1, cmp);
 85     MST = 0;
 86     for(int i = 1; i <= m; ++i)
 87     {
 88         int id = r[i];
 89         int fu = find(U[id]);
 90         int fv = find(V[id]);
 91         if(fu != fv) {
 92             MST += w[id];
 93             f[ fu ] = fv;
 94             addedge(U[id], V[id], w[id]);
 95             addedge(V[id], U[id], w[id]);
 96         }
 97     }
 98 }
 99 int main() {
100     init();
101     mst();
102     BFS(1);
103 
104     for(int i = 1; i <= m; ++i) {
105         printf("%I64d
", MST - LCA(U[i], V[i]) + w[i]);
106     }
107     return 0;
108 }

View Code