题解 P4180 【【模板】严格次小生成树[BJWC2010]】
hicc0305
2018-10-30 15:51:26
求次小生成树，首先我们要求出最小生成树
然后，我们显然要拿没被选中的边来替换最小生成树中的边。
当我们把一条边加进去的时候，必然会形成一个环，那么很简单，我们只用找出环上除新加边的且不与新加相等边最大边，差值就是加这条边的最小增加量。然后所有最小增加量再加上最小生成树的边权值，就是答案了。
同理，我们也可以这样求第三小生成树，而再小的话就不行了，因为有可能替换两条边要比替换一条边要小。而求第三小的话是不会出现这种情况的，原因如下：假设替换a增加量最小，b次小，c最大，显然a<b<a+b,而a+b是否小于c是不能确定的。
然后怎么找出环上除新加边的且不与新加相等边最大边呢？对于边(u,v)我们找出u,v的LCA：l，然后用倍增处理u->l,v->l两条路径，即可。但由于可能出现最大值和新加边的权值相等，所以我们还要预处理次大边，如下：
预处理：f不多说，v1为j倍增处理出的最大值，v2就是次大值。
```cpp
for(int i=1;i<=21;i++)
for(int j=1;j<=n;j++)
{
f[i][j]=f[i-1][f[i-1][j]];
v1[i][j]=max(v1[i-1][j],v1[i-1][f[i-1][j]]);
v2[i][j]=max(v2[i-1][j],v2[i-1][f[i-1][j]]);
if(v1[i-1][j]>v1[i-1][f[i-1][j]]) v2[i][j]=max(v2[i][j],v1[i-1][f[i-1][j]]);
else if(v1[i-1][j]<v1[i-1][f[i-1][j]]) v2[i][j]=max(v2[i][j],v1[i-1][j]);
}
```
对于一条环的处理：
```
int get(int u,int v,int k)
{
int res=-INF;
for(int i=20;i>=0;i--)
if(dep[f[i][u]]>=dep[v])
{
if(k!=v1[i][u]) res=max(res,v1[i][u]);//不一样就和最大的取max
else res=max(res,v2[i][u]);//否则和次大的取max
u=f[i][u];
}
return res;
}
for(int i=1;i<=m;i++)
if(!e[i].in)
{
int l=Lca(e[i].x,e[i].y);
int res=max(get(e[i].x,l,e[i].z),get(e[i].y,l,e[i].z));
ans=min(ans,e[i].z-res);
}
```
OK，全部的代码：
```cpp
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define int long long
using namespace std;
const long long INF=214748364700000;
int n,m,sum=0,cnt=0;
int fa[100100],f[30][100100],dep[100100],v1[30][100100],v2[30][100100];
int head[200100],nxt[200100],to[200100],val[200100];
struct Edge
{
int x,y,z,in;
}e[300100];
bool cmp(Edge a,Edge b) {return a.z<b.z;}
int find(int x)
{
if(fa[x]==x) return x;
return fa[x]=find(fa[x]);
}
void addedge(int x,int y,int z)
{
cnt++;
nxt[cnt]=head[x];
head[x]=cnt;
to[cnt]=y;
val[cnt]=z;
}
void dfs(int u,int pre)
{
for(int i=head[u];i!=-1;i=nxt[i])
{
int v=to[i];
if(v==pre) continue;
dep[v]=dep[u]+1,f[0][v]=u;
v1[0][v]=val[i],v2[0][v]=-INF;
dfs(v,u);
}
}
int Lca(int x,int y)
{
if(dep[x]<dep[y]) swap(x,y);
for(int i=20;i>=0;i--)
if(dep[f[i][x]]>=dep[y]) x=f[i][x];
if(x==y) return x;
for(int i=20;i>=0;i--)
if(f[i][x]!=f[i][y]) x=f[i][x],y=f[i][y];
return f[0][x];
}
int get(int u,int v,int k)
{
int res=-INF;
for(int i=20;i>=0;i--)
if(dep[f[i][u]]>=dep[v])
{
if(k!=v1[i][u]) res=max(res,v1[i][u]);
else res=max(res,v2[i][u]);
u=f[i][u];
}
return res;
}
signed main()
{
memset(head,-1,sizeof(head));
scanf("%lld%lld",&n,&m);
for(int i=1;i<=m;i++)
scanf("%lld%lld%lld",&e[i].x,&e[i].y,&e[i].z);
sort(e+1,e+m+1,cmp);
for(int i=1;i<=n;i++)
fa[i]=i;
for(int i=1;i<=m;i++)
{
if(cnt==2*n-2) break;
int fx=find(e[i].x),fy=find(e[i].y);
if(fx!=fy)
{
fa[fx]=fy;
sum+=e[i].z;
e[i].in=1;
addedge(e[i].x,e[i].y,e[i].z);
addedge(e[i].y,e[i].x,e[i].z);
}
}
dep[1]=1;dfs(1,0);
for(int i=1;i<=21;i++)
for(int j=1;j<=n;j++)
{
f[i][j]=f[i-1][f[i-1][j]];
v1[i][j]=max(v1[i-1][j],v1[i-1][f[i-1][j]]);
v2[i][j]=max(v2[i-1][j],v2[i-1][f[i-1][j]]);
if(v1[i-1][j]>v1[i-1][f[i-1][j]]) v2[i][j]=max(v2[i][j],v1[i-1][f[i-1][j]]);
else if(v1[i-1][j]<v1[i-1][f[i-1][j]]) v2[i][j]=max(v2[i][j],v1[i-1][j]);
}
int ans=INF;
for(int i=1;i<=m;i++)
if(!e[i].in)
{
int l=Lca(e[i].x,e[i].y);
int res=max(get(e[i].x,l,e[i].z),get(e[i].y,l,e[i].z));
ans=min(ans,e[i].z-res);
}
printf("%lld",ans+sum);
return 0;
}
```