次小生成樹

次小生成樹

我們已經熟知了求最小生成樹的方法，用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;  
}