[NOI 2014]魔法森林

佚名 6年前 (2019-05-16) 随笔 1899人围观抢沙发百度已收录

题目大意：

一个有\(n\)个点，\(m\)条边的无向图，每条边都另有两个权值\(a_i\)和\(b_i\)，一开始有两个指数，\(A\)，\(B\)，如果你的\(A>=a_i,B>=b_i\)那么你就可以通过这条边，求\(A+B\)的最小值。

大体思路：

\(LCT\)裸题。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

注意到有两个指数，那我们肯定要先通过各种方法搞掉一个指数，再去维护另一个指数，比如用\(CDQ\)分治，当然这题只要用个\(sort\)，再维护一棵最小生成树，即可。

把边按\(a_i\)排序，然后一条一条地加入\(LCT\)，如果目前这条边的两端以在同一连通块中，那么加入这条边之后肯定就会变成一个环，那么如果原连通块中\(b_i\)最大的一条边比该边的\(b_i\)小，那么就把最大的那条边删了，让该边加入即可。

一个边权转点权的无脑方法：

两点之间在加入另一个点，只有中间新加入的这个点有点权，点权就是这条边的权值。

#include<bits/stdc++.h>
using namespace std;
const int N=200005,inf=1e6+7;
int w[N],val[N],fa[N],rev[N],ch[N][2],Max[N],p[N];
int n,m,opt,x,y,ans,t;
struct edge{
    int u,v,a,b;
} e[N];
bool cmp(edge a,edge b){return a.a<b.a;}
int find(int x){return p[x]==x?x:p[x]=find(p[x]);}
int wh(int x){return ch[fa[x]][1]==x;}
bool isrt(int x){return ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x;}
void rever(int x){rev[x]^=1,swap(ch[x][0],ch[x][1]);}
void update(int x){
    Max[x]=x;
    if (ch[x][0]&&val[Max[ch[x][0]]]>val[Max[x]]) Max[x]=Max[ch[x][0]];
    if (ch[x][1]&&val[Max[ch[x][1]]]>val[Max[x]]) Max[x]=Max[ch[x][1]];
}
void pushdown(int x){
    if (rev[x]){
        if (ch[x][0]) rever(ch[x][0]);
        if (ch[x][1]) rever(ch[x][1]);
        rev[x]=0;
    }
}
void Allpushdown(int x){
    if (!isrt(x)) Allpushdown(fa[x]);
    pushdown(x);
}
void rotate(int x){
    int y=fa[x],z=fa[y],c=wh(x);
    if (!isrt(y)) ch[z][wh(y)]=x;
    fa[x]=z;
    ch[y][c]=ch[x][c^1];
    fa[ch[y][c]]=y;
    ch[x][c^1]=y;
    fa[y]=x;
    update(y),update(x);
}
void splay(int x){
    Allpushdown(x);
    for (;!isrt(x);rotate(x))
        if (!isrt(fa[x])) rotate(wh(fa[x])==wh(x)?fa[x]:x);
}
void access(int x){
    for (int y=0;x;y=x,x=fa[x]) splay(x),ch[x][1]=y,update(x);
}
void makert(int x){
    access(x),splay(x),rever(x);
}
void link(int x,int y){
    makert(x),fa[x]=y;
}
void cut(int x,int y){
    makert(x),access(y),splay(y);
    fa[x]=ch[y][0]=0,update(y);
}
int query(int x,int y){
    makert(x),access(y),splay(y);
    return Max[y];
}
int main(){
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++) scanf("%d%d%d%d",&e[i].u,&e[i].v,&e[i].a,&e[i].b);
    sort(e+1,e+1+m,cmp);
    for (int i=1;i<=n;i++) p[i]=i; 
    ans=inf;
    for (int i=1;i<=m;i++){
        int u=e[i].u,v=e[i].v;
        if (find(u)==find(v)){
            t=query(u,v);
            if (e[i].b<val[t]){
                cut(t,e[t-n].u);
                cut(t,e[t-n].v);
            }
            else{
                if (find(1)==find(n)) ans=min(ans,e[i].a+val[query(1,n)]);
                continue;
            }
        } else p[find(u)]=find(v);
        val[i+n]=e[i].b,Max[i+n]=i+n;
        link(u,i+n),link(i+n,v);
        if (find(1)==find(n)) ans=min(ans,e[i].a+val[query(1,n)]);
    }
    if (ans==inf) puts("-1"); else printf("%d\n",ans);
    return 0;
}