https://www.luogu.org/problemnew/show/P4180#sub
严格次小生成树,即不等于最小生成树中的边权之和最小的生成树
首先求出最小生成树,然后枚举所有不在最小生成树里的边,找出最小增量,
如果将一条不在最小生成树里的边加入生成树,那么就会形成环
如图,绿色为最小生成树,如果将红色边加入,就在紫色区域构成了环
那么现在增量就是用红色边的边权 - 紫色区域内最大的绿色边的边权
这里红色边的边权一定大于等于紫色区域内最大的绿色边的边权(由最小生
成树的构成可知),如果红色边的边权 = 紫色区域内最大的绿色边的边权
那么紫色区域就要取次大值(因为要求严格次小)
套路:将这个环分成 lca (红色边的u,v的lca) 到 u 和 lca 到 v 两条路径
倍增最大值和次大值即可
Answer = 最小生成树 + 最小增量
#include <iostream> #include <cstdio> #include <algorithm> #include <cmath> using namespace std; const int N = 1e5 + 10; #define gc getchar() int n, m, now = 1; struct Node { int u, v, w, is_in; bool operator <(const Node a)const { return w < a.w; } } E[N * 3]; struct Node_2{int u, v, w, nxt;} G[(N * 3) << 1]; int fa[N][30], Max[N][30], Tmax[N][30], deep[N], head[N], father[N]; int Mi[30]; #define LL long long LL Answer; int Min = 1e9; inline int read() { int x = 0; char c = gc; while(c < '0' || c > '9') c = gc; while(c >= '0' || c >= '9') x = x * 10 + c - '0', c = gc; return x; } void Add(int u, int v, int w) {G[now].v = v; G[now].w = w; G[now].nxt = head[u]; head[u] = now ++;} int Getfa(int x) {return father[x] == x ? x : father[x] = Getfa(father[x]);} void Mst() { int js(0); for(int i = 1; js != n - 1; i ++) { int u = E[i].u, v = E[i].v, fu = Getfa(u), fv = Getfa(v); if(fu != fv) { father[fu] = fv; js ++; E[i].is_in = 1; Answer += (LL)E[i].w; Add(E[i].u, E[i].v, E[i].w); Add(E[i].v, E[i].u, E[i].w); } } } void Dfs(int x, int f_, int dep) { deep[x] = dep; for(int i = 1; ; i ++) { if(deep[x] - Mi[i] < 0) break; fa[x][i] = fa[fa[x][i - 1]][i - 1]; Max[x][i] = max(Max[x][i - 1], Max[fa[x][i - 1]][i - 1]); if(Max[x][i - 1] == Max[fa[x][i - 1]][i - 1]) Tmax[x][i] = max(Tmax[x][i - 1], Tmax[fa[x][i - 1]][i - 1]); else Tmax[x][i] = max(min(Max[x][i - 1], Max[fa[x][i - 1]][i - 1]), max(Tmax[x][i - 1], Tmax[fa[x][i - 1]][i - 1])); } for(int i = head[x]; ~ i; i = G[i].nxt) { int v = G[i].v; if(v != f_) {fa[v][0] = x; Max[v][0] = G[i].w; Tmax[v][0] = -1; Dfs(v, x, dep + 1);} } } int Lca(int x, int y) { if(deep[x] < deep[y]) swap(x, y); int k = deep[x] - deep[y]; for(int i = 0; i <= 17; i ++) if(k >> i & 1) x = fa[x][i]; if(x == y) return x; for(int i = 17; i >= 0; i --) if(fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i]; return fa[x][0]; } void Work(int s, int t, int w_) { int m1 = 0, m2 = 0, k = deep[s] - deep[t]; for(int i = 0; i <= 17; i ++) { if(k >> i & 1) { m2 = max(m2, Tmax[s][i]); if(Max[s][i] > m1) {m2 = max(m2, m1); m1 = Max[s][i];} } } if(m1 == w_) Min = min(Min, w_ - m2); else Min = min(Min, w_ - m1); } int main() { n = read(); m = read(); for(int i = 1; i <= n; i ++) head[i] = -1, father[i] = i; Mi[0] = 1; for(int i = 1; i <= 17; i ++) Mi[i] = Mi[i - 1] * 2; for(int i = 1; i <= m; i ++) {E[i].u = read(), E[i].v = read(), E[i].w = read();} sort(E + 1, E + m + 1); Mst(); Dfs(1, 0, 1); for(int i = 1; i <= m; i ++) { if(!E[i].is_in) { int u = E[i].u, v = E[i].v; int L = Lca(u, v); Work(u, L, E[i].w); Work(v, L, E[i].w); } } cout << Answer + Min; return 0; }
树剖版,cogs AC,luogu 80
线段树维护区间最大和严格次大
/* 次小生成树的链剖实现 */ #include <iostream> #include <cstdio> #include <algorithm> #include <cmath> using namespace std; const int N = 1e5 + 10; #define gc getchar() #define LL long long int n, m, now = 1, Tim, Min = (int)1e9, Max1, Max2; int head[N], deep[N], top[N], fa[N], tree[N], bef[N], size[N], son[N], dad[N], data[N]; int Max[N << 2], Tmax[N << 2]; struct Node { int u, v, w, is_in; bool operator <(const Node a) const {return w < a.w;} }E[N << 2]; struct Node_2{int u, v, w, nxt;} G[N << 1]; LL Answer; inline int read() { int x = 0; char c = gc; while(c < '0' || c > '9') c = gc; while(c >= '0' || c >= '9') x = x * 10 + c - '0', c = gc; return x; } void Add(int u, int v, int w) {G[now].u = u; G[now].v = v; G[now].w = w; G[now].nxt = head[u]; head[u] = now ++;} int Getfa(int x) {return dad[x] == x ? x : dad[x] = Getfa(dad[x]);} void Dfs_find_son(int u, int f_, int dep) { fa[u] = f_; deep[u] = dep; size[u] = 1; for(int i = head[u]; ~ i; i = G[i].nxt) { int v = G[i].v; if(v != f_) { data[v] = G[i].w; Dfs_find_son(v, u, dep + 1); size[u] += size[v]; if(size[v] > size[son[u]]) son[u] = v; } } } void Dfs_un(int u, int tp) { top[u] = tp; tree[u] = ++ Tim; bef[Tim] = u; if(!son[u]) return ; Dfs_un(son[u], tp); for(int i = head[u]; ~ i; i = G[i].nxt) { int v = G[i].v; if(v != fa[u] && v != son[u]) Dfs_un(v, v); } } void Mst() { int js(0); for(int i = 1; js != n - 1; i ++) { int u = E[i].u, v = E[i].v, fu = Getfa(u), fv = Getfa(v); if(fu != fv) { dad[fu] = fv; js ++; E[i].is_in = 1; Answer += (LL)E[i].w; Add(E[i].u, E[i].v, E[i].w); Add(E[i].v, E[i].u, E[i].w); } } } #define lson jd << 1 #define rson jd << 1 | 1 void Push_up(int jd) { if(Max[lson] == Max[rson]) { Max[jd] = Max[lson]; Tmax[jd] = max(Tmax[lson], Tmax[rson]); } else { Max[jd] = max(Max[lson], Max[rson]); Tmax[jd] = max(min(Max[lson], Max[rson]), max(Tmax[lson], Tmax[rson])); } } void Build_tree(int l, int r, int jd) { if(l == r) { Max[jd] = data[bef[l]]; Tmax[jd] = -1; return ; } int mid = (l + r) >> 1; Build_tree(l, mid, lson); Build_tree(mid + 1, r, rson); Push_up(jd); } int Lca(int x, int y) { int tp1 = top[x], tp2 = top[y]; while(tp1 != tp2) { if(deep[tp1] < deep[tp2]) swap(x, y), swap(tp1, tp2); x = fa[tp1]; tp1 = top[x]; } return deep[x] < deep[y] ? x : y; } void Sec_G(int l, int r, int jd, int x, int y) { if(x <= l && r <= y) { if(Max[jd] > Max1) {Max2 = max(Max1, Tmax[jd]); Max1 = Max[jd];} else if(Max[jd] == Max1) Max2 = max(Max2, Tmax[jd]); else Max2 = max(Max2, Max[jd]); return ; } int mid = (l + r) >> 1; if(x <= mid) Sec_G(l, mid, lson, x, y); if(y > mid) Sec_G(mid + 1, r, rson, x, y); } void Sec_G_imp(int x, int y, int w_) { int tp1 = top[x], tp2 = top[y], M1 = 0, M2 = 0; while(tp1 != tp2) { if(deep[tp1] < deep[tp2]) swap(x, y), swap(tp1, tp2); Max1 = 0, Max2 = 0; Sec_G(1, n, 1, tree[tp1], tree[x]); if(Max1 > M1) {M2 = max(M1, Max2), M1 = Max1;} else if(Max1 == M1) M2 = max(M2, Max2); else M2 = max(M2, Max1); x = fa[tp1]; tp1 = top[x]; } if(x == y) return ; if(deep[x] < deep[y]) swap(x, y); Max1 = 0, Max2 = 0; Sec_G(1, n, 1, tree[y] + 1, tree[x]); if(Max1 > M1) {M2 = max(M1, Max2), M1 = Max1;} else if(Max1 == M1) M2 = max(M2, Max2); else M2 = max(M2, Max1); if(M1 == w_) Min = min(Min, w_ - M2); else Min = min(Min, w_ - M1); } int main() { n = read(), m = read(); for(int i = 1; i <= n; i ++) dad[i] = i, head[i] = -1; for(int i = 1; i <= m; i ++) {E[i].u = read(), E[i].v = read(), E[i].w = read();} sort(E + 1, E + m + 1); Mst(); Dfs_find_son(1, 0, 1); Dfs_un(1, 1); Build_tree(1, n, 1); for(int i = 1; i <= m; i ++){ if(!E[i].is_in) { int u = E[i].u, v = E[i].v; Sec_G_imp(u, v, E[i].w); } } std:: cout << Answer + Min; return 0; }