题解 P2387 【[NOI2014]魔法森林】

题解

我们都生活在阴沟里，但仍有人在仰望星空。——奥斯卡·王尔德

前天写了一下午+晚上运输计划结果到最后还是95，最后换种写法才A掉
然后昨天下午到今天上午一直在肝魔法森林，真的现在看到LCT就头大
这道一年前我觉得这辈子都不可能写的题终于被干掉了|>_<|

• 我的做法是按照a为第一关键字排序，之后按顺序加边。
  每次我们判断边w的端点(x,y)是否连通
  1.如果不连通，直接连接，
  2.否则在x->y的路径上找到b值最大的边f，
  此时判断，
  A. f.b小于w.b，跳过
  B. f.b大于w.b，把f删去，在生成树中加入w。

• 上述操作进行完后都要判断 1，n是否连通。如果连通我们就更新ans
  其中ans=min(ans,a+val[sa(1,n)])。
  (a为w.a，val[sa(1,n)]为1到n路径上最大的b值)

• 还有一点就是边权怎么办？LCT不好处理边信息啊！
  所以我们把边变成点，例如边w的端点为x,y，加边时我们就把w的编号变为w+n，val[w+n]=w.b。然后Link(x,w+n),Link(y,w+n);Cut同理
  然后我们开一个数组id记录子树中最大val值，每次pushup更新即可

结合Bei-S's 博客食用更佳哦~

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+20;
const int INF=0x7ffffff;
int head[N],cnt,fa[N],p[N],son[N][2],id[N],mx[N],rev[N],val[N],siz[N],n,m,ans=INF;
struct ii{
    int x,y,a,b;
}e[N*2];
inline bool isroot(int x){return son[fa[x]][0]!=x&&son[fa[x]][1]!=x;}
inline void pushdown(int x){
    if(!rev[x]) return ;
    rev[x]=0;rev[son[x][0]]^=1;rev[son[x][1]]^=1;
    swap(son[x][0],son[x][1]);
}
inline void pushup(int x){//更新最大边编号 
    if(val[x]>val[id[son[x][0]]]&&val[x]>val[id[son[x][1]]]) id[x]=x;//如果当前点(边化的点)比儿子的边权都大，直接赋为x 
    else id[x]=val[id[son[x][0]]]>val[id[son[x][1]]]?id[son[x][0]]:id[son[x][1]];//否则谁大赋谁的 
}
inline void rotate(int x){
    pushdown(fa[x]);pushdown(x);
    int y=fa[x],z=fa[y],t=son[y][0]==x;
    if(!isroot(y)) son[z][y==son[z][1]]=x;
    fa[x]=z;
    son[y][!t]=son[x][t];fa[son[x][t]]=y;
    son[x][t]=y;fa[y]=x;
    pushup(y);pushup(x);
}
inline void splay(int x){
    pushdown(x);
    while(!isroot(x)){
        int y=fa[x],z=fa[y];
        if(!isroot(y)) (son[y][0]==x)^(son[z][0]==y)?rotate(x):rotate(y);
        rotate(x);
    }
}
inline void Access(int x){
    for(int y=0;x;y=x,x=fa[x]){
        splay(x);
        son[x][1]=y;
        pushup(x);
    }
}
inline void Makeroot(int x){
    Access(x);
    splay(x);
    rev[x]^=1;
}
inline void Split(int x,int y){
    Makeroot(x);
    Access(y);
    splay(x);
}
inline void Link(int x,int y){
    Makeroot(x);
    fa[x]=y;
}
inline void Cut(int x,int y){
    Split(x,y);
    splay(x);
    fa[y]=son[x][1]=0;
}
inline int Find(int x){
    Access(x);
    splay(x);
    while(son[x][0]) x=son[x][0];
    return x;
}
inline int sa(int x,int y){//查询x，y路径中b值最大的边的编号 
    Makeroot(x);
    Access(y);
    splay(y);//把x，y放入一颗splay中，把y splay到根，更新后id[y]即为所求 
    return id[y];
}
bool cmp(ii l,ii r) {return l.a<r.a;}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++) scanf("%d%d%d%d",&e[i].x,&e[i].y,&e[i].a,&e[i].b);
    sort(e+1,e+1+m,cmp);//按照a排序 
    for(int i=1;i<=m;i++){
        int u=e[i].x,v=e[i].y,a=e[i].a,b=e[i].b;
        if(Find(u)==Find(v)){//如果边的端点已经连通，他们之间最大b值 
            int f=sa(u,v);//f为U,V间最大(b值)边的编号 
            if(val[f]<=b) {//如果val[f]<=b 直接查询即可 
                if(Find(1)==Find(n))
                    ans=min(ans,a+val[sa(1,n)]);
                continue;
            }
            Cut(f,e[f-n].x);Cut(f,e[f-n].y);//否则我们需要删去这条边，注意删去后记得连边，我写在下面了 
        }
        val[i+n]=b;//如果 端点不连通 或者 新加入边的b值比边的端点间最大的b值小 ，我们都要连上这条边 
        id[i+n]=i+n;//把边化点，val记为b，id记作i+n 
        Link(u,i+n);Link(v,i+n);
        if(Find(1)==Find(n))//更新答案 
            ans=min(ans,a+val[sa(1,n)]);
    }
    cerr<<ans;
    if(ans==INF) printf("-1");
    else printf("%d",ans);
}