BZOJ 1977[BeiJing2010组队]次小生成树 Tree

描述：

就是求一个次小生成树的边权和

传送门

题解

我们先构造一个最小生成树，把树上的边记录下来。

然后再枚举每条非树边(u, v, val)，在树上找出u 到v 路径上的最小边$g_0$ 和严格次小边 $g_1$

如果$val > g_0$就可以考虑把$g_0$ 替换成$val$ 并记录答案。

如果$val = g_0$ 就把$g_1$替换成$val$ 记录答案。

然后我们就需要快速求出树链上的最小和次小边，需要用树上倍增求LCA类似的方法求。

定义$g[0][ i ][ j ]$ 表示从$j$ 到第 $2^i$ 辈祖先中的最小边， $g[1][ i ][ j ] $表示从$j$ 到第$2^i$ 辈祖先中的次小边，满足以下关系：

1: $g[0][ i ][ j ] = max( g[0][ i - 1][ j ], g[0][ i - 1][ f[i - 1][ j ]]) $

2 :$ g[1][ i ][ j ] = max( g[1][ i - 1][ j ], g[1][ i - 1 ][ f[i - 1][ j ]]) $ 当$g[0][i - 1][ j ] = g[0][ i - 1][ f[i - 1][ j ]] $

3: $ g[1][ i ][ j ] = max(g[0][ i - 1][ j ], g[1][ i - 1][ f[i - 1][ j ]])$ 当$g[0][i - 1][ j ] < g[0][ i - 1][ f[i - 1][ j ]] $

4: $ g[1][ i ][ j ] = max(g[1][ i - 1][ j ], g[0][ i - 1][ f[i - 1][ j ]])$ 当$g[0][i - 1][ j ] > g[0][ i - 1][ f[i - 1][ j ]] $

倍增求树链上的最小和次小值时同理合并

题解

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<algorithm>
  4 #define rd read()
  5 #define rep(i,a,b) for(register int i = (a); i <= (b); ++i)
  6 #define per(i,a,b) for(register int i = (a); i >= (b); --i)
  7 #define ll long long
  8 using namespace std;
  9 
 10 const int N = 5e5;
 11 const int inf = ~0U >> 1;
 12 
 13 int n, m;
 14 ll sum, ans = 1e18;
 15 int fa[N], f[30][N], g[2][30][N], dep[N];
 16 int head[N], tot;
 17 
 18 struct edge {
 19     int nxt, to, val;
 20 }e[N << 2];
 21 
 22 struct node {
 23     int u, v, val, mk;
 24 }E[N << 2];
 25 
 26 inline int read() {
 27     int X = 0, p = 1; char c = getchar();
 28     for(; c > '9' || c < '0'; c = getchar()) if(c == '-') p = -1;
 29     for(; c >= '0' && c <= '9'; c = getchar()) X = X * 10 + c - '0';
 30     return X * p;
 31 }
 32 
 33 inline void added(int u, int v, int val) {
 34     e[++tot].to = v;
 35     e[tot].nxt = head[u];
 36     e[tot].val = val;
 37     head[u] = tot;
 38 }
 39 
 40 inline void add(int u, int v, int val) {
 41     added(u, v, val); added(v, u, val);
 42 }
 43 
 44 inline int fd(int x) {
 45     return fa[x] == x ? x : fa[x] = fd(fa[x]);
 46 }
 47 
 48 inline int cmp(const node &A, const node &B) {
 49     return A.val < B.val;
 50 }
 51 
 52 inline void dfs(int u) {
 53     for(int i = head[u]; i; i = e[i].nxt) {
 54         int nt = e[i].to;
 55         if(nt == f[0][u]) continue;
 56         f[0][nt] = u;
 57         g[0][0][nt] = e[i].val;
 58         g[1][0][nt] = -inf;
 59         dep[nt] = dep[u] + 1;
 60         dfs(nt);
 61     }
 62 }
 63 
 64 inline void LCA(int x, int y, int &a, int &b) {
 65     int g0, g1;
 66     if(dep[x] < dep[y]) swap(x, y);
 67     for(int i = 20; ~i; --i) if(dep[f[i][x]] >= dep[y]) {
 68         g0 = g[0][i][x]; g1 = g[1][i][x];
 69         if(g0 == a) b = max(b, g1);
 70         if(g0 > a) b = max(a, g1);
 71         if(g0 < a) b = max(g0, b);
 72         a = max(a, g0);
 73         x = f[i][x];
 74     }
 75     for(int i = 20; ~i; --i) if(f[i][x] != f[i][y]) {
 76         g0 = g[0][i][x]; g1 = g[1][i][x];
 77         if(g0 == a) b = max(b, g1);
 78         if(g0 > a) b = max(a, g1);
 79         if(g0 < a) b = max(g0, b);
 80         a = max(a, g0);
 81 
 82         g0 = g[0][i][y]; g1 = g[1][i][y];
 83         if(g0 == a) b = max(b, g1);
 84         if(g0 > a) b = max(a, g1);
 85         if(g0 < a) b = max(g0, b);
 86         a = max(a, g0);
 87         x = f[i][x]; y = f[i][y];
 88     }
 89 
 90     g0 = g[0][0][x]; g1 = g[1][0][x];
 91     if(g0 == a) b = max(b, g1);
 92     if(g0 > a) b = max(a, g1);
 93     if(g0 < a) b = max(g0, b);
 94     a = max(a, g0);
 95 
 96     g0 = g[0][0][y]; g1 = g[1][0][y];
 97     if(g0 == a) b = max(b, g1);
 98     if(g0 > a) b = max(a, g1);
 99     if(g0 < a) b = max(g0, b);
100     a = max(a, g0);    
101 }
102 
103 int main()
104 {
105     n = rd; m = rd;
106     rep(i, 1, n) fa[i] = i;
107     rep(i, 1, m) {
108         int u = rd, v = rd, val = rd;
109         E[i].u = u; E[i].v = v; E[i].val = val; E[i].mk = 0;
110     }
111     sort(E+1, E+1+m, cmp);
112     rep(i, 1, m) {
113         int x = fd(E[i].u), y = fd(E[i].v);
114         if(x == y) continue;
115         sum += E[i].val;
116         fa[y] = x;
117         E[i].mk = 1;
118         add(E[i].u, E[i].v, E[i].val);
119     }
120     dep[1] = 1;
121     dfs(1);
122     rep(i, 1, 20) rep(j, 1, n) {
123         f[i][j] = f[i - 1][f[i - 1][j]];
124         g[0][i][j] = max(g[0][i - 1][j], g[0][i - 1][f[i - 1][j]]);
125         int tmp = -inf;
126         if(g[0][i - 1][j] == g[0][i - 1][f[i - 1][j]]) tmp = max(g[1][i - 1][j], g[1][i - 1][f[i - 1][j]]);
127         if(g[0][i - 1][j] < g[0][i - 1][f[i - 1][j]]) tmp = max(g[0][i - 1][j], g[1][i - 1][f[i - 1][j]]);
128         if(g[0][i - 1][j] > g[0][i - 1][f[i - 1][j]]) tmp = max(g[1][i - 1][j], g[0][i - 1][f[i - 1][j]]);
129         g[1][i][j] = tmp;
130     }
131     rep(i, 1, m) if(!E[i].mk) {
132         int x = E[i].u, y = E[i].v, g0 = -inf, g1 = -inf;
133         LCA(x, y, g0, g1);
134         if(E[i].val == g0 && g1 != -inf) ans = min(ans, sum + E[i].val - g1);
135         if(E[i].val > g0) ans = min(ans, sum + E[i].val - g0);
136     }
137     printf("%lld
",ans);
138 }

View Code