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

· · 题解

题目大意

找到一棵严格次小生成树，边权和大于最小生成树。

n\le10^5,m\le 3\cdot 10^5,w_i\le10^9

思路

比较厉害的一道题，几乎完全覆盖了提高组的知识点，没有一点超出提高组的范围。

因为是次小生成树，一定是与最小生成树有很大关联的，所以先用 kruskal 求出最小生成树。

考虑每条边，假设该边在次小生成树上，那么必须删去两点之间的一条边，但不能与这条边权值相同，因为这个过程一定是增加权值，所以只能进行一次。

具体的，维护数组数组 fa_{u,i},fimx_{u,i},semx_{u,i} 表示 u 往上 2^i 的的祖先，u 到 2^i 祖先这段的最大值、次大值。在求 LCA 的预处理同时处理，求 LCA 是同时维护答案。

时间复杂度：\Theta(m\log n+n\log n)

code

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=a;i>=n;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
const int mod=998244353;
const ll mod2=1ll*mod*mod;
const int maxn=3e5+10;
int quick(int a,int b){int res=1;a%=mod;assert(b>=0); for(;b;b>>=1){if(b&1)res=1ll*res*a%mod;a=1ll*a*a%mod;}return res;}
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int n,m,pa[maxn][23],dep[maxn],fimx[maxn][23],semx[maxn][23],FA[maxn];
ll ans=1e18,mst;
vector<PII> eg[maxn];
struct edge{
    int u,v,w,qu;
    bool operator<(const edge x)const{
        return w<x.w;
    }
}e[maxn];
int find(int u){
    return (FA[u]==u)?u:FA[u]=find(FA[u]);
}
void kruskal(){
    rep(i,1,n) FA[i]=i;
    sort(e+1,e+m+1);
    rep(i,1,m){
        int u=find(e[i].u),v=find(e[i].v);
        if(u==v) continue;
        mst+=e[i].w;
        FA[u]=v;
        e[i].qu=1;
        eg[e[i].u].pb(mp(e[i].v,e[i].w));
        eg[e[i].v].pb(mp(e[i].u,e[i].w));
    } 
}
void dfs(int u,int fa){
    dep[u]=dep[fa]+1;
    pa[u][0]=fa;
    for(int i=0;i<SZ(eg[u]);i++){
        int v=eg[u][i].fi;
        if(v==fa) continue;
        fimx[v][0]=eg[u][i].se;
        dfs(v,u);
    }
}
void init(){
    rep(j,1,18)
        rep(i,1,n){
            pa[i][j]=pa[pa[i][j-1]][j-1];
            fimx[i][j]=max(fimx[i][j-1],fimx[pa[i][j-1]][j-1]);
            semx[i][j]=max(semx[i][j-1],semx[pa[i][j-1]][j-1]);
            if(fimx[i][j-1]!=fimx[pa[i][j-1]][j-1])
                semx[i][j]=max(semx[i][j],min(fimx[i][j-1],fimx[pa[i][j-1]][j-1]));
        }
}
void query(int u,int v,int w){
    int maxn1=0,maxn2=0;
    if(dep[u]>dep[v]) swap(u,v);
    per(i,18,0) 
        if(dep[v]>=dep[u]+(1<<i)){
            if(maxn1^fimx[v][i]) maxn2=max(maxn2,min(maxn1,fimx[v][i]));
            maxn1=max(maxn1,fimx[v][i]);
            maxn2=max(maxn2,semx[v][i]);
            v=pa[v][i];
        }
    if(u==v){
        ll tmp=w-((w==maxn1)?maxn2:maxn1);
        ans=min(ans,mst+tmp);
        return ;
    }
    per(i,18,0){
        if(pa[u][i]!=pa[v][i]){
            if(maxn1^fimx[u][i]) maxn2=max(maxn2,min(maxn1,fimx[u][i]));
            maxn1=max(maxn1,fimx[u][i]);
            maxn2=max(maxn2,semx[u][i]);
            if(maxn1^fimx[v][i]) maxn2=max(maxn2,min(maxn1,fimx[v][i]));
            maxn1=max(maxn1,fimx[v][i]);
            maxn2=max(maxn2,semx[v][i]);
            v=pa[v][i],u=pa[u][i];
        }
    }
    if(maxn1^fimx[u][0]) maxn2=max(maxn2,min(maxn1,fimx[u][0]));
    maxn1=max(maxn1,fimx[u][0]);
    maxn2=max(maxn2,semx[u][0]);
    if(maxn1^fimx[v][0]) maxn2=max(maxn2,min(maxn1,fimx[v][0]));
    maxn1=max(maxn1,fimx[v][0]);
    maxn2=max(maxn2,semx[v][0]);
    ll tmp=w-((w==maxn1)?maxn2:maxn1);
    ans=min(ans,mst+tmp);
    return ;
}
int main(){
    cin>>n>>m;
    rep(i,1,m) scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
    kruskal();
    dfs(1,0);
    init();
    rep(i,1,m) 
        if(!e[i].qu){
            query(e[i].u,e[i].v,e[i].w);
        }
    cout<<ans;
    return 0;
}