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

· · 题解

Kurskal找最小生成树

然后枚举一条非树边

找边所在的环上的最大值和次大值

这题有一个十分大材小用的写法

就是把在找一条链上的最大值和次大值

用可持久化线段树来维护（主席树）

好像有哪个大佬提到过这种写法……

#include<bits/stdc++.h>
#define N 100005
#define mid ((l+r)>>1)
using namespace std;
int n,m;
vector<int>P[N],C[N];
struct edge{
    int a,b,c;
    bool operator<(const edge &_)const{return c<_.c;}
}E[N*3];
int vis[N*3];
int fat[N];
int getfa(int x){return x==fat[x]?x:fat[x]=getfa(fat[x]);}
long long Kurskal(){
    for(int i=1;i<=n;i++)fat[i]=i;
    sort(E+1,E+m+1);
    long long ans=0;
    for(int i=1;i<=m;i++){
        int x=getfa(E[i].a),y=getfa(E[i].b);
        if(x==y)continue;
        vis[i]=1;
        ans+=E[i].c;
        fat[x]=y;
        P[E[i].a].push_back(E[i].b);
        C[E[i].a].push_back(E[i].c);
        P[E[i].b].push_back(E[i].a);
        C[E[i].b].push_back(E[i].c);
    }
    return ans;
}
int fa[N][20],de[N];
int res[N*40];
int R[N*40];
int L[N*40];
int B[N*3],rt[N];
int tt,tot;
int update(int l,int r,int x,int p) {
    int rot=++tt;
    L[rot]=L[p];
    R[rot]=R[p];
    res[rot]=res[p]+1;
    if(l>=r)return rot;
    if(l<r) {
        if(x<=mid)L[rot]=update(l,mid,x,L[p]);
        else R[rot]=update(mid+1,r,x,R[p]);
    }
    return rot;
}
int query(int l,int r,int u,int v,int w,int k) {
    if(l>=r)return l;
    int x=res[L[v]]+res[L[u]]-2*res[L[w]];
    if(x>=k)return query(l,mid,L[u],L[v],L[w],k);
    else return query(mid+1,r,R[u],R[v],R[w],k-x);
}
int query2(int l,int r,int u,int v,int w,int k){
    if(l>=r)return res[u]+res[v]-2*res[w];
    if(k<=mid)return query2(l,mid,L[u],L[v],L[w],k);
    else return query2(mid+1,r,R[u],R[v],R[w],k);
}
void dfs(int p,int lastt,int dep,int cost){
    int t=lower_bound(B+1, B+1+tot, cost)-B; 
    rt[p]=update(1,tot,t,rt[lastt]);
    fa[p][0]=lastt;
    de[p]=dep;
    for(int i=0;i<(int)P[p].size();i++){
        int y=P[p][i];
        if(y==lastt)continue;
        dfs(y,p,dep+1,C[p][i]);
    }
}
int Lca(int a, int b) {
    if(de[a]>de[b])swap(a,b);
    for(int j=19;j>=0;j--)
        if(de[fa[b][j]]>=de[a])b=fa[b][j];
//  printf("a=%d b=%d\n",a,b);
    if(a==b)return a;
    for(int j=19;j>=0;j--){
        if(fa[b][j]!=fa[a][j]){
            b=fa[b][j];
            a=fa[a][j];
        }
    }
    return fa[a][0];
}
void solve(){
    tt=0;
    scanf("%d %d",&n,&m);
    for(int a,b,c,i=1;i<=m;i++){
        scanf("%d %d %d",&a,&b,&c);
        E[i]=(edge){a,b,c};
        B[i]=c;
    }
    long long ans=Kurskal();
//  printf("%lld\n",ans);
    sort(B+1,B+m+1);
    tot = unique(B+1, B+1+m)-B-1;
    dfs(1,0,1,E[1].c);
    for(int i=1;i<=19;i++)
        for(int j=1;j<=n;j++)
            fa[j][i]=fa[fa[j][i-1]][i-1];
    int mi=0x3f3f3f3f;
    for(int i=1;i<=m;i++){
        if(vis[i])continue;
        int lca=Lca(E[i].a,E[i].b);
        int t=lower_bound(B+1, B+1+tot, E[i].c)-B;
        int sum=res[rt[E[i].a]]+res[rt[E[i].b]]-2*res[rt[lca]];
        int kk=query(1,tot,rt[E[i].a],rt[E[i].b],rt[lca],sum);
        if(t>kk){
            mi=min(mi,B[t]-B[kk]);
            continue;
        }
        sum-=query2(1,tot,rt[E[i].a],rt[E[i].b],rt[lca],kk);
        if(sum==0)continue;
        kk=query(1,tot,rt[E[i].a],rt[E[i].b],rt[lca],sum);
//      printf("%d %d\n",B[t],B[kk]);
        mi=min(mi,B[t]-B[kk]);
    }
    printf("%lld\n",ans+mi);
}
int main(){
    solve();
    return 0;
}