zcmimi's blog
查看原题

点击跳转

LCT动态维护最小生成树

维护链上的最大值和次大值

先找出最小生成树,然后枚举剩下的边,找出相差最小的,得出答案

这题还可以用kruskal生成树+倍增(或树剖)做,常数会小很多

#include<bits/stdc++.h>
#define il __inline__ __attribute__ ((always_inline))
il int min(int x,int y){return x<y?x:y;}
il int max(int x,int y){return x>y?x:y;}
namespace IN{const int str=1<<20;static char in_buf[str],*in_s,*in_t;bool __=0;inline char gc(){return (in_s==in_t)&&(in_t=(in_s=in_buf)+fread(in_buf,1,str,stdin)),in_s==in_t?EOF:*in_s++;}template<typename T>inline void in(T &x){if(__)return;char c=gc();bool f=0;while(c!=EOF&&(c<'0'||c>'9'))f^=(c=='-'),c=gc();if(c==EOF){__=1;return;}x=0;while(c!=EOF&&'0'<=c&&c<='9')x=x*10+c-48,c=gc();if(c==EOF)__=1;if(f)x=-x;}template<typename T,typename ... arr>inline void in(T &x,arr & ... y){in(x),in(y...);}}using namespace IN;
const int N=100001;
int n,m,s[N<<1],S[N<<1],c[2][N<<1],f[N<<1],v[N<<1];
bool rev[N<<1];
#define ls c[0][x]
#define rs c[1][x]
il void pu(int x){
    if(s[ls]>s[rs])s[x]=s[ls],S[x]=max(S[ls],s[rs]);
    else if(s[rs]>s[ls])s[x]=s[rs],S[x]=max(s[ls],S[rs]);
    else s[x]=s[ls],S[x]=max(S[ls],S[rs]);

    if(v[x]>s[x])S[x]=s[x],s[x]=v[x];
    else if(v[x]!=s[x]&&v[x]>S[x])S[x]=v[x];
}
il void pr(int x){rev[x]^=1,ls^=rs,rs^=ls,ls^=rs;}
il void pd(int x){
    if(rev[x]){
        if(ls)pr(ls);
        if(rs)pr(rs);
        rev[x]=0;
    }
}
il int g(int x){return c[1][f[x]]==x;}
il int nrt(int x){return c[0][f[x]]==x||c[1][f[x]]==x;}
void pda(int x){if(nrt(x))pda(f[x]);pd(x);}
il void rotate(int x){
    int y=f[x],z=f[y],l=g(x),r=!l,w=c[r][x];
    if(nrt(y))c[g(y)][z]=x;
    c[r][x]=y,c[l][y]=w;
    if(w)f[w]=y;
    f[x]=z,f[y]=x;
    pu(y),pu(x);
}
il void splay(int x){
    for(pda(x);nrt(x);rotate(x))if(nrt(f[x]))
        rotate(g(x)^g(f[x])?x:f[x]);
}
il void access(int x){
    for(int y=0;x;x=f[y=x])
        splay(x),rs=y,pu(x);
}
il void mrt(int x){access(x),splay(x),pr(x);}
struct edge{
    int x,y,w;
    bool operator<(edge t){return w<t.w;}
}e[300001];
int fa[N];
int gf(int x){return x==fa[x]?x:(fa[x]=gf(fa[x]));}
int main(){
    in(n,m);
    for(int i=1;i<=m;++i)in(e[i].x,e[i].y,e[i].w);
    std::sort(e+1,e+m+1);
    long long tot=0;int x,y,id=n,ans=-1u>>1;
    for(int i=1;i<=n;++i)fa[i]=i;
    for(int i=1;i<=m;++i){
        x=e[i].x,y=e[i].y;
        if(gf(x)!=gf(y)){
            fa[fa[x]]=fa[y];
            tot+=e[i].w;
            v[++id]=e[i].w;
            mrt(x),mrt(y),f[x]=f[y]=id;
        }
        else{
            mrt(x),access(y),splay(y);
            ans=min(ans,e[i].w-(e[i].w>s[y]?s[y]:S[y]));
        }
    }
    printf("%lld\n",tot+ans);
}
LG 4180 [BJWC2010]严格次小生成树
comment评论
Search
search