次小生成树学习笔记

学习笔记"/>

次小生成树学习笔记

次小生成树有严格次小生成树和非严格次小生成树之分。常见的是严格次小生成树。

严格次小生成树的定义如下：

如果最小生成树选择的边集是 E M E_M EM​，严格次小生成树选择的边集是 E S E_S ES​，那么需要满足：( v a l u e ( e ) value(e) value(e) 表示边 e e e 的权值) ∑ e ∈ E M v a l u e ( e ) < ∑ e ∈ E S v a l u e ( e ) \sum_{e \in E_M}value(e)<\sum_{e \in E_S}value(e) ∑e∈EM​​value(e)<∑e∈ES​​value(e)。

——P4180 [BJWC2010] 严格次小生成树

求严格次小生成树的方法主要有倍增、树剖、LCT 等。这里介绍所用算法较基础的 Kruskal+倍增+LCA 的方法。

显然，次小生成树是在最小生成树的基础上替换一条边之后形成的。

容易想到一种思路：对于每一条非树边，尝试把它加入最小生成树中。此时图中出现了一个环，删去环中边权最大的树边即可。由于要求的是严格次小，为了避免最大树边等于加入的这条非树边的边权的情况，还需要维护次大树边。

维护次大树边可以用倍增。用 g 1 ( i , j ) , g 2 ( i , j ) g_1(i,j),g_2(i,j) g1​(i,j),g2​(i,j) 分别表示从 i i i 到 i i i 的 2 j 2^j 2j 级父亲的路径上的边权最大值、次大值。 g 1 g_1 g1​ 直接维护即可， g 2 g_2 g2​ 的 max ⁡ \max max 选择需要分情况讨论：

• g 1 g_1 g1​ 的 ( i , i + 2 j − 1 ) , ( i + 2 j − 1 , i + 2 j ) (i,i+2^{j-1}),(i+2^{j-1},i+2^j) (i,i+2j−1),(i+2j−1,i+2j) 两段最大值相等，维护 g 2 g_2 g2​ 的两段最大值。
• g 1 ( i , j − 1 ) > g 1 ( i + 2 j − 1 , j − 1 ) g_1(i,j-1)>g_1(i+2^{j-1},j-1) g1​(i,j−1)>g1​(i+2j−1,j−1)，则次大值不可能在后面的区间出现，维护前面区间的次大值和后面区间的最大值取 max ⁡ \max max 即可。
• g 1 ( i , j − 1 ) < g 1 ( i + 2 j − 1 , j − 1 ) g_1(i,j-1)<g_1(i+2^{j-1},j-1) g1​(i,j−1)<g1​(i+2j−1,j−1)，则次大值不可能在前面的区间出现，维护后面区间的次大值和前面区间的最大值取 max ⁡ \max max 即可。

时间复杂度 O ( n log ⁡ n + m log ⁡ n ) O(n\log n+m\log n) O(nlogn+mlogn)。

#include <bits/stdc++.h>
using namespace std;
#define int long longconst int maxn=1e5+5,maxm=6e5+5;
int head[maxn],g1[maxn][25],g2[maxn][25],f[maxn][25],dep[maxn],cnt,N,M,fa[maxn],sum;
struct edge1{int u,v,w;}e1[maxm];
struct edge2{int to,nxt,w;}e2[maxm];
bool vis[maxm];bool cmp(edge1 a,edge1 b){return a.w<b.w;}int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}void add(int x,int y,int z){e2[++cnt]={y,head[x],z},head[x]=cnt;}void kruskal()
{sort(e1+1,e1+M+1,cmp);int tot=0;for(int i=1;i<=M;i++){int fu=find(e1[i].u),fv=find(e1[i].v);if(fu!=fv) tot++,fa[fu]=fv,sum+=e1[i].w,add(e1[i].u,e1[i].v,e1[i].w),add(e1[i].v,e1[i].u,e1[i].w),vis[i]=1;if(tot==N-1) break;}
}void dfs(int x,int fa)
{dep[x]=dep[fa]+1,f[x][0]=fa;for(int i=1;i<=20;i++){f[x][i]=f[f[x][i-1]][i-1];g1[x][i]=max(g1[f[x][i-1]][i-1],g1[x][i-1]);if(g1[f[x][i-1]][i-1]==g1[x][i-1]) g2[x][i]=max(g2[x][i-1],g2[f[x][i-1]][i-1]);else if(g1[f[x][i-1]][i-1]>g1[x][i-1]) g2[x][i]=max(g1[x][i-1],g2[f[x][i-1]][i-1]);else g2[x][i]=max(g2[x][i-1],g1[f[x][i-1]][i-1]);}for(int i=head[x];i;i=e2[i].nxt){if(e2[i].to==fa) continue;g1[e2[i].to][0]=e2[i].w;dfs(e2[i].to,x);}
}int lca(int x,int y)
{if(dep[x]<dep[y]) swap(x,y);for(int i=20;i>=0;i--) if(dep[f[x][i]]>=dep[y]) x=f[x][i];if(x==y) return x;for(int i=20;i>=0;i--)if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];return f[x][0];
}int getmx(int x,int rt,int w)
{int ans=0;for(int i=20;i>=0;i--)if(dep[f[x][i]]>=dep[rt]){if(g1[x][i]==w) ans=max(ans,g2[x][i]);else ans=max(ans,g1[x][i]);x=f[x][i];}return ans;
}signed main()
{cin>>N>>M;for(int i=1;i<=M;i++) cin>>e1[i].u>>e1[i].v>>e1[i].w;for(int i=1;i<=N;i++) fa[i]=i;kruskal();dfs(1,0);int ans=LLONG_MAX;for(int i=1;i<=M;i++){if(e1[i].u==e1[i].v||vis[i]) continue;int mx=getmx(e1[i].u,lca(e1[i].u,e1[i].v),e1[i].w),my=getmx(e1[i].v,lca(e1[i].u,e1[i].v),e1[i].w);if(max(mx,my)!=e1[i].w) ans=min(ans,sum+e1[i].w-max(mx,my));}cout<<ans<<endl;// for(int i=1;i<=N;i++) cout<<g1[i][0]<<' '<<g2[i][0]<<endl;return 0;
}