P2387 [NOI2014]魔法森林

题目

P2387 [NOI2014]魔法森林

这题目花了点时间题解没图，其中一些操作不够简洁，常数比较大，都说\(LCT\)常数小(时限\(3000ms\),最大点\(500ms\))，反正过了

做法

首先考虑做法：排序\(a\)，顺序加边，然后动态维护最大\(b\)(使生成树最小，其中贡献为最大的\(b\))

这题是动态的，所以考虑\(LCT\)，但不同的是维护边权，根据我们图论的技巧，把边转点(拆成三点\(u,x,v\))，其中\(x\)存下边权

我们在添边的时候，如果不构成环(\(u,v\)实现没联通)之间添进去，构成环就利用\(LCT\)把这个环最大的\(b\)提出来跟这条边比然后替换

添边\((u,x,v)\)：\(u\)和\(v\)分别拉成各自联通块的子树，然后\(u-x-v\)轻边连起来

删边\((u,x,v)\)：\(u,v\)拉链，中间就只剩下\(x\)了嘛，\(x\)提到根然后删掉

总结一下：贪心+\(LCT\)动态维护最大权边

My complete code

#include<cstdio>
#include<cstring>
#include<string>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<set>
using namespace std;
typedef int LL;
const LL maxn=1e6,B=(1<<17),inf=0x3f3f3f3f;
inline LL Read(){
    LL x(0),f(1);char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+c-'0',c=getchar();
    return x*f;
}
struct E{
    LL u,v,a,b;
    bool operator <(const E &x)const{
        return a<x.a;
    }
}dis[maxn];
LL n,ans=inf,m;
LL son[maxn][2],fa[maxn],mx[maxn],r[maxn],sta[maxn];
inline void Update(LL x){
    mx[x]=x;
    if(dis[mx[son[x][0]]].b>dis[mx[x]].b) mx[x]=mx[son[x][0]];
    if(dis[mx[son[x][1]]].b>dis[mx[x]].b) mx[x]=mx[son[x][1]];
}
inline bool Notroot(LL x){
    return son[fa[x]][0]==x||son[fa[x]][1]==x;
}
inline void Pushr(LL x){
    swap(son[x][0],son[x][1]),r[x]^=1;
}
inline void Pushdown(LL x){
    if(r[x]){
        if(son[x][0])Pushr(son[x][0]);
        if(son[x][1])Pushr(son[x][1]);
        r[x]=0;
    }
}
inline void Rotate(LL x){
    LL y(fa[x]),z(fa[y]),lz(son[y][1]==x);
    if(Notroot(y)) son[z][son[z][1]==y]=x;fa[x]=z;
    son[y][lz]=son[x][lz^1];
    if(son[y][lz]) fa[son[y][lz]]=y;
    son[x][lz^1]=y,fa[y]=x;
    Update(y),Update(x);
}
inline void Splay(LL x){
    LL y(x),top(0); sta[++top]=y;
    while(Notroot(y)) sta[++top]=y=fa[y];
    while(top) Pushdown(sta[top--]);
    while(Notroot(x)){
        y=(fa[x]);
        if(Notroot(y)){
            LL z(fa[y]);
            if(((son[z][1]==y)^(son[y][1]==x))==0) Rotate(y);
            else Rotate(x);
        }Rotate(x);
    }
}
inline void Access(LL x){
    for(LL y=0;x;y=x,x=fa[x])
        Splay(x),son[x][1]=y,Update(x);
}
inline void Makeroot(LL x){
    Access(x),Splay(x),Pushr(x);
}
inline void Split(LL x,LL y){
    Makeroot(x),Access(y),Splay(y);
}
inline LL Findroot(LL x){
    Access(x),Splay(x);
    while(son[x][0]) x=son[x][0];
    return x;
}
inline void Link(LL x){
    LL u(dis[x].u),v(dis[x].v);
    Makeroot(u),Makeroot(v);
    fa[v]=x,fa[x]=u;
}
inline void Delet(LL x){
    LL u(dis[x].u),v(dis[x].v);
    Split(u,v);Splay(x);
    son[x][0]=son[x][1]=fa[son[x][0]]=fa[son[x][1]]=0;
}
int main(){
    n=Read(),m=Read();
    for(LL i=1;i<=m;++i){
        dis[i]=(E){Read(),Read(),Read(),Read()};
        dis[i].u|=B,dis[i].v|=B;
    }
    sort(dis+1,dis+1+m);
    for(LL i=1;i<=m;++i){
        LL u(dis[i].u),v(dis[i].v);
        if(Findroot(u)!=Findroot(v))
            Link(i);
        else{
            Makeroot(u),Access(v),Splay(v);
            if(dis[i].b<dis[mx[v]].b){
                Delet(mx[v]);
                Link(i);
            }
        }
        Makeroot(1|B);
        if((1|B)==Findroot(n|B))
            ans=min(ans,dis[i].a+dis[mx[n|B]].b);
    }
    if(ans<inf)
        printf("%d\n",ans);
    else
        printf("-1");
    return 0;
}

P2387 [NOI2014]魔法森林

原文：https://www.cnblogs.com/y2823774827y/p/10328014.html