【模板】严格次小生成树[BJWC2010]

洛咕

题意:给定一张\(n\)个点\(m\)条边的无向图,求无向图的严格次小生成树.\(n<=1e5,m<=3e5.\)

分析:先\(kruskal\)求出图的最小生成树,设边权之和为\(sum.\)我们把在最小生成树中的\(n-1\)条边先加入图中,对新图(这棵最小生成树)\(dfs\),预处理出\(f[i][j],maxn[i][j],minn[i][j]\)分别表示\(i\)的\(2^j\)级祖先,\(i\)到其\(2^j\)级祖先的路径上的最大边权,\(i\)到其\(2^j\)级祖先的路径上的次大边权.

然后对于剩下的\(m-(n-1)\)条边,我们每次枚举一条边,设该边两个端点分别为\(x,y\),权值为\(z\),找到\(x->y\)路径上的最大边权\(maxx\),则答案可以更新为\(ans=min(ans,sum-maxx+z)\),相当于删去这条边权最大的边,加入我们当前枚举的这条边,从而保证严格次小.

\(long\) \(long\)

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline ll read(){
    ll x=0,o=1;char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')o=-1,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*o;
}
const int N=1e5+5;
const int M=3e5+5;
ll n,m,sum,ans,maxn[N][25],minn[N][25];
ll fa[N],bj[M],dep[N],f[N][25];
ll tot,head[N],nxt[M],to[M],w[M];
struct edge{ll x,y,z;}a[M];
inline bool cmp(edge x,edge y){return x.z<y.z;}
inline int find(int x){
    if(x==fa[x])return x;
    return fa[x]=find(fa[x]);
}
inline void add(int a,int b,ll c){
    nxt[++tot]=head[a];head[a]=tot;
    to[tot]=b;w[tot]=c;
}
inline void kruskal(){//最小生成树模板
    sort(a+1,a+m+1,cmp);int k=0;//边权从小到达排序
    for(int i=1;i<=n;++i)fa[i]=i;//初始化并查集
    for(int i=1;i<=m;++i){
        int x=find(a[i].x),y=find(a[i].y);
        if(x==y)continue;
        add(a[i].x,a[i].y,a[i].z);
        add(a[i].y,a[i].x,a[i].z);//重新建图
        sum+=a[i].z;bj[i]=1;//把这条边标记为加入了最小生成树
        fa[x]=y;if(++k==n-1)break;
    }
}
inline void dfs(int u,int fa){//LCA的预处理
    for(int j=1;j<=20;++j){
         f[u][j]=f[f[u][j-1]][j-1];
         maxn[u][j]=max(maxn[u][j-1],maxn[f[u][j-1]][j-1]);
         minn[u][j]=max(minn[u][j-1],minn[f[u][j-1]][j-1]);
         if(maxn[u][j-1]>maxn[f[u][j-1]][j-1])minn[u][j]=max(minn[u][j],maxn[f[u][j-1]][j-1]);
         else if(maxn[u][j-1]<maxn[f[u][j-1]][j-1])minn[u][j]=max(minn[u][j],maxn[u][j-1]);
    }
    for(ll i=head[u];i;i=nxt[i]){
        ll v=to[i];if(v==fa)continue;
        f[v][0]=u;maxn[v][0]=w[i];minn[v][0]=-1e18;
        dep[v]=dep[u]+1;dfs(v,u);
    }
}
inline ll LCA(ll x,ll y){
    if(dep[x]<dep[y])swap(x,y);
    for(int j=20;j>=0;--j)
        if(dep[f[x][j]]>=dep[y])x=f[x][j];
    if(x==y)return x;
    for(int j=20;j>=0;--j)
        if(f[x][j]!=f[y][j])x=f[x][j],y=f[y][j];
    return f[x][0];
}
inline ll query(ll x,ll y,ll z){
    ll Ans=-1e18;
    for(int j=20;j>=0;--j)
        if(dep[f[x][j]]>=dep[y]){
            if(z!=maxn[x][j])Ans=max(Ans,maxn[x][j]);
            else Ans=max(Ans,minn[x][j]);
            x=f[x][j];
        }
    return Ans;
}
int main(){
    n=read();m=read();
    for(int i=1;i<=m;++i)a[i].x=read(),a[i].y=read(),a[i].z=read();
    kruskal();dfs(1,0);ans=1e18;
    for(int i=1;i<=m;++i)
        if(!bj[i]){//枚举没有加入最小生成树的边
            ll x=a[i].x,y=a[i].y,z=a[i].z,lca=LCA(x,y);
            ll max1=query(x,lca,z),max2=query(y,lca,z);//先分别找两个点到lca的最大值
            ans=min(ans,sum-max(max1,max2)+z);//两者中取最大值加入图中
        }
    printf("%lld\n",ans);
    return 0;
}

那些初始化赋值,一定要赋值为超级大,\(1e9\)都会挂.

【模板】严格次小生成树[BJWC2010]

原文：https://www.cnblogs.com/PPXppx/p/11574533.html