次小生成树

次小生成树

我们已经熟知了求最小生成树的方法，用kruskal,prim算法都可以搞
那么我们如何求次小生成树呢？
这里次小生成树的定义是

边权和严格大于最小生成树的边权和最小的生成树

求解方法

次小生成树嘛，肯定和最小生成树脱不了关系
那么我们首先求出最小生成树

接下来，一个比较显然的思路是
枚举每一条未加入最小生成树的边，加入最小生成树，同时在最小生成树中删除边权最大的边
如果你想到了这里并写出了代码，那么恭喜你
你在里成功还有一步之遥成功掉进坑里了
比如下面的例子

蓝边表示最小生成树中的边，黄边表示新加入的边
在这种情况下，如果仅仅记录最大值的话，得到的答案一定是错的
所以我们还要记录严格小于最大值的最大值
当产生冲突的时候我们需要删除严格小于最大值的最大值

优化

但是这样效率太低了，每一次查询都是\(O(n)\)的
有没有更好的方法呢？

不要忘了，最小生成树它是一棵树呀
树的链上最大最小值操作，你想到了什么？

没错！树上倍增

我们在倍增的过程中记录下最大值和严格小于最大值的最大值

这样每次查询的复杂度就变成\(log(n)\)啦

总结

流程

整个算法的流程大概是

1. 求出最小生成树
2. 构造出倍增数组
3. 每次树上倍增查询

时间复杂度

用kruskal是\(O(m\log m+Q\log (n))\)
用prim是\(O(n\log n+Q\log (n))\)
Q为询问次数

代码

放一道裸题

// luogu-judger-enable-o2
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
#define int long long 
using namespace std;
const int MAXN=400001;
const int INF=1e15+10;
inline int read()
{
    char c=getchar();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
struct Edge
{
    int u,v,w;
}E[MAXN];
int Enum=1;
void Add(int x,int y,int z)
{
    E[Enum].u=x;
    E[Enum].v=y;
    E[Enum].w=z;Enum++;
}
struct node
{
    int u,v,w,nxt;
}edge[MAXN];
int head[MAXN];
int num=1;
int N,M;
int fa[MAXN],vis[MAXN],sum;
int deep[MAXN],f[MAXN][21],maxx[MAXN][21],minx[MAXN][21];
void AddEdge(int x,int y,int z)
{
    edge[num].u=x;
    edge[num].v=y;
    edge[num].w=z;
    edge[num].nxt=head[x];
    head[x]=num++;
}
int find(int x)
{
    if(fa[x]==x) return fa[x];
    else return fa[x]=find(fa[x]);
}
int unionn(int x,int y)
{
    int fx=find(x),fy=find(y);
    fa[fx]=fy;
}
int comp(const Edge &a,const Edge &b)
{
    return a.w<b.w;
}
void Kruskal()
{
    sort(E+1,E+Enum,comp);
    int tot=0;
    for(int i=1;i<=Enum-1;i++)
    {
        int x=E[i].u,y=E[i].v;
        if(find(x)!=find(y)) 
        {
            unionn(x,y),tot++,sum+=E[i].w,vis[i]=1;
            AddEdge(x,y,E[i].w);AddEdge(y,x,E[i].w);
        }
        if(tot==N-1) break;
    }
}
void dfs(int now,int fa)
{
    for(int i=head[now];i!=-1;i=edge[i].nxt)
    {
        if(edge[i].v==fa) continue;
        deep[edge[i].v]=deep[edge[i].u]+1;
        f[edge[i].v][0]=now;
        maxx[edge[i].v][0]=edge[i].w;
        dfs(edge[i].v,now);
    }
}
void pre()
{
    for(int i=1;i<=18;i++)
    {
        for(int j=1;j<=N;j++)
        {
            f[j][i]=f[ f[j][i-1] ][i-1];
            maxx[j][i]=max(maxx[j][i-1],maxx[ f[j][i-1] ][i-1]);
            minx[j][i]=max(minx[j][i-1],minx[ f[j][i-1] ][i-1]);
            if(maxx[j][i-1]>maxx[ f[j][i-1] ][i-1]) minx[j][i]=max(minx[j][i],maxx[ f[j][i-1] ][i-1]);
            else minx[j][i]=max(minx[j][i],maxx[j][i-1]);
        }
    }
}
int LCA(int x,int y)
{
    if(deep[x]<deep[y]) swap(x,y);
    for(int i=18;i>=0;i--)
        if(deep[ f[x][i] ] >= deep[y] ) 
            x=f[x][i];
    if(x==y) return x;
    for(int i=18;i>=0;i--)
        if(f[x][i] != f[y][i])
            x=f[x][i],y=f[y][i];
    return f[x][0];
}
int findmax(int x,int lca,int val)
{
    int ans=0;
    for(int i=18;i>=0;i--)
    {
        if(deep[ f[x][i] ] >= deep[lca]) 
        {
            if(maxx[x][i]==val) ans=max(ans,minx[x][i]);
            else ans=max(ans,maxx[x][i]);
            x=f[x][i];
        }
    }
    return ans;
}
void work()
{
    int ans=INF;
    for(int i=1;i<=Enum-1;i++)
    {
        if(vis[i]) continue;
        int x=E[i].u,y=E[i].v,z=E[i].w;
        int lca=LCA(x,y);
        int lmx=findmax(x,lca,z);
        int rmx=findmax(y,lca,z);
        if(max(lmx,rmx)!=z)
        ans=min(ans,sum+z-max(lmx,rmx));
    }
    printf("%lld",ans);
}
main()
{  
    #ifdef WIN32
    freopen("a.in","r",stdin);
    #else
    #endif
    N=read(),M=read();
    memset(head,-1,sizeof(head));
    for(int i=1;i<=N;i++) fa[i]=i;
    for(int i=1;i<=M;i++)
    {
        int x=read(),y=read(),z=read();
        Add(x,y,z);
    }
    Kruskal();
    deep[1]=1;
    dfs(1,0);
    pre();
    work();
    return 0;  
}