BZOJ 3669 魔法老林 LCT

链接：【BZOJ 3669】
题意：一个无向图，每条边都有A,B两种权值，找出一条最优路径使得1~n路径上的两个权值的瓶颈之和最小。
思路：对于每条边按照A为关键字从小到大排序，枚举A的瓶颈加入边，若边的两点之间联通，则找出B最大的边并比较，若大于当前B，则将该边删去，否则不加入这条边。
代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int max_n=400010;
#define NIL pool
struct Node{
    int val;
    int pos,mpos;
    bool root,rev;
    int l,r;
    Node *lch,*rch,*fa;
    Node(){
        root=rev=false;
    }
    Node(int _val,int _pos,Node *_lch,Node *_rch,Node *_fa)
    :val(_val),pos(_pos),lch(_lch),rch(_rch),fa(_fa){
        mpos=pos;
        root=true;
        rev=false;
    }
}pool[max_n],*sp;
struct LCT{
    Node *node[max_n],*stk[max_n];
    int now_cnt;
    LCT(){}
    int max1(int a,int b){
        if(node[a]->val>node[b]->val)return a;
        return b;
    }
    void init(){
        new(NIL)Node(0,0,NIL,NIL,NIL);
        sp=NIL;
        node[0]=new(++sp)Node(0,0,NIL,NIL,NIL);
    }
    void build(int n){
        now_cnt=n;
        for(int i=1;i<=n;i++){
            node[i]=new(++sp)Node(0,0,NIL,NIL,NIL);
        }
    }
    void update(Node *t){
        if(t==NIL)return;
        t->mpos=max1(t->pos,max1(t->lch->mpos,t->rch->mpos));
    }
    void reverse(Node *t){
        if(t==NIL)return;
        t->rev^=1;
        swap(t->lch,t->rch);
    }
    void pushdown(Node *t){
        if(t==NIL)return;
        if(t->rev){
            t->rev=false;
            reverse(t->lch);
            reverse(t->rch);
        }
    }
    void zig(Node *t){
        Node *f=t->fa,*c=t->rch;
        if(f->root)t->root=true,f->root=false;
        else (f->fa->lch==f?f->fa->lch:f->fa->rch)=t;
        t->fa=f->fa,t->rch=f,f->lch=c,f->fa=t,c->fa=f;
        update(f);
    }
    void zag(Node *t){
        Node *f=t->fa,*c=t->lch;
        if(f->root)t->root=true,f->root=false;
        else (f->fa->lch==f?f->fa->lch:f->fa->rch)=t;
        t->fa=f->fa,t->lch=f,f->rch=c,f->fa=t,c->fa=f;
        update(f);
    }
    void splay(Node *t){
        Node *p=t;
        int top=0;
        stk[top]=t;
        while(!p->root){
            stk[++top]=p->fa;
            p=p->fa;
        }
        while(top>=0){
            pushdown(stk[top--]);
        }
        while(!t->root){
            if(t->fa->root){
                if(t->fa->lch==t)zig(t);
                else zag(t);
            }
            else {
                if(t->fa->fa->lch==t->fa){
                    if(t->fa->lch==t)zig(t->fa),zig(t);
                    else zag(t),zig(t);
                }
                else {
                    if(t->fa->lch==t)zig(t),zag(t);
                    else zag(t->fa),zag(t);
                }

            }
        }
        update(t);
    }
    void evert(Node *t){
        t=expose(t);
        reverse(t);
    }
    Node* expose(Node *t){
        Node *p=t,*q=NIL;
        while(p!=NIL){
            splay(p);
            p->rch->root=true;
            p->rch=q;
            p->rch->root=false;
            update(p);
            q=p;
            p=p->fa;
        }
        return q;
    }
    Node * getroot(Node *t){
        t=expose(t);
        while(1){
            if(t->lch!=NIL){
                t=t->lch;
            }
            else {
                return t;
            }
        }
    }
    void cut(int a,int b){
        evert(node[b]);
        expose(node[a]);
        splay(node[a]);
        if(node[a]->lch==node[b]){
            node[a]->lch->fa=NIL;
            node[a]->lch->root=true;
            node[a]->lch=NIL;
            update(node[a]);
        }
    }
    void link(int a,int b){
        if(getroot(node[a])==getroot(node[b])){
            cut_it(a,b);
        }
        evert(node[b]);
        splay(node[b]);
        node[b]->fa=node[a];
        expose(node[b]);
    }
    void Link(int a,int b,int val){
        apy_edge(a,b,val);
        link(a,now_cnt);
        link(b,now_cnt);
    }
    void apy_edge(int a,int b,int val){
        node[++now_cnt]=new(++sp)Node(val,now_cnt,NIL,NIL,NIL);
        node[now_cnt]->l=a;
        node[now_cnt]->r=b;
    }
    void cut_it(int a,int b){
        Node *p=node[b],*q=NIL;
        expose(node[a]);
        int ret;
        while(p!=NIL){
            splay(p);
            if(p->fa==NIL){
                ret=max1(p->pos,max1(p->rch->mpos,q->mpos));
            }
            p->rch->root=true;
            p->rch=q;
            q->root=false;
            update(p);
            q=p;
            p=p->fa;
        }
        cut(ret,node[ret]->l);
        cut(ret,node[ret]->r);
    }
    int querry(int a,int b){
        if(getroot(node[a])!=getroot(node[b]))return 1000000000;
        Node *p=node[b],*q=NIL;
        expose(node[a]);
        int ret;
        while(p!=NIL){
            splay(p);
            if(p->fa==NIL){
                ret=max1(p->pos,max1(p->rch->mpos,q->mpos));
            }
            p->rch->root=true;
            p->rch=q;
            q->root=false;
            update(p);
            q=p;
            p=p->fa;
        }
        return node[ret]->val;
    }
}T;

int rk[max_n];
int op[max_n][4];
bool cmp(int a,int b){
    return op[a][2]<op[b][2];
}
int main(){
    int n,m;
    while(~scanf("%d%d",&n,&m)){
        int ans=1e9;
        T.init();
        T.build(n);
        for(int i=0;i<m;i++){
            scanf("%d%d%d%d",op[i],op[i]+1,op[i]+2,op[i]+3);
            rk[i]=i;
        }
        sort(rk,rk+m,cmp);
        for(int i=0;i<m;i++){
            int tp=rk[i];
            int ttp=T.querry(op[tp][0],op[tp][1]);
            if(ttp>op[tp][3]){
                T.Link(op[tp][0],op[tp][1],op[tp][3]);
                ans=min(ans,op[tp][2]+T.querry(1,n));
            }
        }
        if(ans==1000000000)ans=-1;
        printf("%d\n",ans);
    }
    return 0;
}