[bzoj3669][Noi2014]魔法森林

Description

为了得到书法大家的真传,小\(E\)同学下定决心去拜访住在魔法森林中的隐士.魔法森林可以被看成一个包含个\(N\)节点\(M\)条边的无向图,节点标号为\(1\dots{N}\),边标号为\(1\dots{M}\).初始时小\(E\)同学在号节点\(1\),隐士则住在号节点\(N\).小\(E\)需要通过这一片魔法森林,才能够拜访到隐士.
魔法森林中居住了一些妖怪.每当有人经过一条边的时候，这条边上的妖怪就会对其发起攻击.幸运的是,在\(1\)号节点住着两种守护精灵:\(A\)型守护精灵与\(B\)型守护精灵.小\(E\)可以借助它们的力量,达到自己的目的.
只要小\(E\)带上足够多的守护精灵,妖怪们就不会发起攻击了.具体来说,无向图中的每一条边\(Ei\)包含两个权值\(A_i\)与\(B_i\).若身上携带的\(A\)型守护精灵个数\(\geq{A_i}\),且\(B\)型守护精灵个数\(\geq{B_i}\),这条边上的妖怪就不会对通过这条边的人发起攻击.当且仅当通过这片魔法森林的过程中没有任意一条边的妖怪向小\(E\)发起攻击,他才能成功找到隐士.
由于携带守护精灵是一件非常麻烦的事,小\(E\)想要知道,要能够成功拜访到隐士,最少需要携带守护精灵的总个数.守护精灵的总个数为\(A\)型守护精灵的个数与\(B\)型守护精灵的个数之和.

Input

第\(1\)行包含两个整数\(N,M\),表示无向图共有\(N\)个节点,\(M\)条边.
接下来\(M\)行,第\(i\)行包含\(4\)个正整数\(X_i,Y_i,A_i,B_i\),描述第\(i\)条无向边.其中\(X_i,Y_i\)为该边两个端点的标号,\(A_i,B_i\)的含义如题所述. 注意数据中可能包含重边与自环.

Output

输出一行一个整数:如果小\(E\)可以成功拜访到隐士,输出小\(E\)最少需要携带的守护精灵的总个数;如果无论如何小\(E\)都无法拜访到隐士,输出-1.

Sample Input

4 5
1 2 19 1
2 3 8 12
2 4 12 15
1 3 17 8
3 4 1 17

Sample Output

32

HINT

\(2\leq{n}\leq50000,0\leq{m}\leq100000,1\leq{Ai,Bi}\leq50000\).

Solution

先将\(A_i\)排序,维护使得\(max\{B_i\}\)最小的生成树.
\(P.S.\)加边\((u,v)\)应比较 \(u->v\) 路径上的\(max\{B_i\}\).

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define N 50010
#define M 100010
using namespace std;
typedef long long ll;
struct edge{
    int l,r,a,b;
}a[M];
struct Splay{
    int c[2],f,id,rev;
}tr[N+M];
int w[N+M],n,m,ans=M;
stack s;
bool flag;
inline int read(){
    int ret=0;char c=getchar();
    while(!isdigit(c))
        c=getchar();
    while(isdigit(c)){
        ret=(ret<<1)+(ret<<3)+c-'0';
        c=getchar();
    }
    return ret;
}
bool operator < (edge x,edge y){
    return x.aw[tr[u].id]) tr[u].id=tr[l].id;
    if(w[tr[r].id]>w[tr[u].id]) tr[u].id=tr[r].id;
}
inline void down(int u){
    if(tr[u].rev){
        tr[u].rev=0;
        tr[tr[u].c[0]].rev^=1;
        tr[tr[u].c[1]].rev^=1;
        swap(tr[u].c[0],tr[u].c[1]);
    }
}
inline bool son(int u){
    return tr[tr[u].f].c[1]==u;
}
inline void ins_p(int f,int u,int c){
    tr[u].f=f;tr[f].c[c]=u;
}
inline bool isroot(int u){
    return tr[tr[u].f].c[0]!=u&&tr[tr[u].f].c[1]!=u;
}
inline void rotate(int u){
    int f=tr[u].f;bool c=son(u);
    if(isroot(f)) tr[u].f=tr[f].f;
    else ins_p(tr[f].f,u,son(f));
    ins_p(f,tr[u].c[c^1],c);
    ins_p(u,f,c^1);
    recnt(f);recnt(u);
}
inline void splay(int u){
    s.push(u);
    for(int v=u;!isroot(v);v=tr[v].f) s.push(tr[v].f);
    while(!s.empty()){
        down(s.top());s.pop();
    }
    while(!isroot(u)){
        if(isroot(tr[u].f)) rotate(u);
        else if(son(tr[u].f)==son(u)){
            rotate(tr[u].f);rotate(u);
        }
        else{
            rotate(u);rotate(u);
        }
    }
}
inline void access(int u){
    for(int lst=0;u;lst=u,u=tr[u].f){
        splay(u);tr[u].c[1]=lst;recnt(u);
        if(lst) tr[lst].f=u;
    }
}
inline int findroot(int u){
    access(u);splay(u);
    while(down(u),tr[u].c[0]) u=tr[u].c[0];
    splay(u);
    return u;
}
inline void makeroot(int u){
    access(u);splay(u);tr[u].rev^=1;
}
inline void select(int u,int v){
    makeroot(u);access(v);splay(v);
}
inline void cut(int u,int v){
    select(u,v);tr[v].c[0]=tr[u].f=0;recnt(v);
}
inline void link(int u,int v){
    makeroot(u);
    tr[u].f=v;
}
inline int ask(int u,int v){
    select(u,v);
    return tr[v].id;
}
inline void Aireen(){
    n=read();m=read();
    for(int i=1;i<=m;++i)
        a[i]=(edge){read(),read(),read(),read()};
    sort(a+1,a+1+m);
    for(int i=1,k;i<=m;++i)
        if(a[i].l!=a[i].r){
            if(findroot(a[i].l)==findroot(a[i].r)){
                k=ask(a[i].l,a[i].r);
                if(w[k]>a[i].b){
                    cut(k,a[k-n].l);
                    cut(k,a[k-n].r);
                }
                else continue;
            }
            tr[n+i].id=n+i;w[n+i]=a[i].b;
            link(a[i].l,n+i);link(a[i].r,n+i);
            if(findroot(1)==findroot(n)) k=ask(1,n),ans=min(ans,a[i].a+w[k]);
        }
    printf("%d\n",ans