为了得到书法大家的真传，小E同学下定决心去拜访住在魔法森林中的隐士。魔法森林可以被看成一个包含个N节点M条边的无向图，节点标号为1..N，边标号为1..M。初始时小E同学在号节点1，隐士则住在号节点N。小E需要通过这一片魔法森林，才能够拜访到隐士。
魔法森林中居住了一些妖怪。每当有人经过一条边的时候，这条边上的妖怪就会对其发起攻击。幸运的是，在号节点住着两种守护精灵：A型守护精灵与B型守护精灵。小E可以借助它们的力量，达到自己的目的。
只要小E带上足够多的守护精灵，妖怪们就不会发起攻击了。具体来说，无向图中的每一条边Ei包含两个权值Ai与Bi。若身上携带的A型守护精灵个数不少于Ai，且B型守护精灵个数不少于Bi，这条边上的妖怪就不会对通过这条边的人发起攻击。当且仅当通过这片魔法森林的过程中没有任意一条边的妖怪向小E发起攻击，他才能成功找到隐士。
由于携带守护精灵是一件非常麻烦的事，小E想要知道，要能够成功拜访到隐士，最少需要携带守护精灵的总个数。守护精灵的总个数为A型守护精灵的个数与B型守护精灵的个数之和。
第1行包含两个整数N,M，表示无向图共有N个节点，M条边。 接下来M行，第行包含4个正整数Xi,Yi,Ai,Bi，描述第i条无向边。其中Xi与Yi为该边两个端点的标号，Ai与Bi的含义如题所述。 注意数据中可能包含重边与自环。
输出一行一个整数：如果小E可以成功拜访到隐士，输出小E最少需要携带的守护精灵的总个数；如果无论如何小E都无法拜访到隐士，输出“-1”（不含引号）。
2<=n<=50,000
0<=m<=100,000
1<=ai ,bi<=50,000首先有一个很简单的想法，假如我们按$a$值从小到大排序，那么随着$a$值的增大，为了保证答案最优，$b$值要相应的减小才行。所以我们可以用$LCT$维护这个过程，当加入一条新边时，若组成环且环上最大的$b$要大于当前边，那么就用这条边替换掉环上的边即可。对于用$LCT$维护边的信息有一个小技巧，就是对于每条边新建一个点，点权等于边权，向两个端点连边
代码：
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #define M 300010 5 #define ls ch[x][0] 6 #define rs ch[x][1] 7 using namespace std; 8 struct point{int u,v,a,b;}e[M]; 9 int n,m,ans=1e9; 10 int fa[M],f[M],maxn[M],val[M],id[M],q[M],rev[M],ch[M][2]; 11 int find(int x) {return fa[x]==x?x:fa[x]=find(fa[x]);} 12 bool cmp(point a1,point a2) {return a1.a<a2.a;} 13 void pushdown(int x){if(rev[x]){rev[ls]^=1,rev[rs]^=1;swap(ls,rs),rev[x]^=1;}} 14 void update(int x) 15 { 16 maxn[x]=val[x],id[x]=x; 17 if(maxn[ls]>maxn[x]) maxn[x]=maxn[ls],id[x]=id[ls]; 18 if(maxn[rs]>maxn[x]) maxn[x]=maxn[rs],id[x]=id[rs]; 19 } 20 int get(int x) {return ch[f[x]][1]==x;} 21 int is_root(int x) {return ch[f[x]][0]!=x&&ch[f[x]][1]!=x;} 22 void rotate(int x) 23 { 24 int old=f[x],oldf=f[old],k=get(x); 25 if(!is_root(old)) ch[oldf][ch[oldf][1]==old]=x; 26 ch[old][k]=ch[x][k^1],f[ch[old][k]]=old; 27 ch[x][k^1]=old,f[old]=x,f[x]=oldf; 28 update(old),update(x); 29 } 30 void splay(int x) 31 { 32 int top=1,fa;q[top]=x; 33 for(int i=x;!is_root(i);i=f[i]) q[++top]=f[i]; 34 for(int i=top;i;i--) pushdown(q[i]); 35 while(!is_root(x)) 36 { 37 if(!is_root(fa=f[x])) 38 rotate(get(x)==get(fa)?fa:x); 39 rotate(x); 40 } 41 } 42 void access(int x) 43 { 44 for(int y=0;x;y=x,x=f[x]) 45 splay(x),ch[x][1]=y,update(x); 46 } 47 void makeroot(int x) {access(x),splay(x),rev[x]^=1;} 48 void spilt(int x,int y) {makeroot(x);access(y);splay(y);} 49 int query(int x,int y) {spilt(x,y);return id[y];} 50 void link(int x,int y) {makeroot(x);f[x]=y;splay(x);} 51 void cut(int x,int y) {spilt(x,y);ch[y][0]=f[x]=0;} 52 int main() 53 { 54 scanf("%d%d",&n,&m); 55 for(int i=1;i<=m;i++) 56 { 57 int x,y,a,b;scanf("%d%d%d%d",&x,&y,&a,&b); 58 e[i]=(point){x,y,a,b}; 59 } 60 sort(e+1,e+1+m,cmp); 61 for(int i=1;i<=n+m;i++) fa[i]=i,id[i]=i; 62 for(int i=1;i<=m;i++) val[i+n]=e[i].b; 63 for(int i=1;i<=m;i++) 64 { 65 int x=e[i].u,y=e[i].v;bool flag=true; 66 if(find(x)==find(y)) 67 { 68 int id=query(x,y); 69 if(val[id]>e[i].b) 70 cut(e[id-n].u,id),cut(e[id-n].v,id); 71 else flag=false; 72 } 73 else fa[find(x)]=find(y); 74 if(flag) link(x,i+n),link(y,i+n); 75 if(find(1)==find(n)) ans=min(ans,e[i].a+val[query(1,n)]); 76 } 77 if(find(1)!=find(n)) puts("-1"); 78 else printf("%d\n",ans); 79 return 0; 80 }
原文：https://www.cnblogs.com/Slrslr/p/10008879.html