Description
题目描述
为了得到书法大家的真传，小 E 同学下定决心去拜访住在魔法森林中的隐士。魔法森林可以被看成一个包含 n 个节点 m 条边的无向图，
节点标号为 1,2,3,…,n，边标号为 1,2,3,…,m。初始时小 E 同学在 1 号节点，隐士则住在 n号节点。小 E 需要通过这一片魔法森林，才能够拜访到隐士。
魔法森林中居住了一些妖怪。每当有人经过一条边的时候，这条边上的妖怪 就会对其发起攻击。幸运的是，在 1号节点住着两种守护精灵：
A 型守护精灵与 B 型守护精灵。小 E 可以借助它们的力量，达到自己的目的。
只要小 E 带上足够多的守护精灵，妖怪们就不会发起攻击了。具体来说，无向图中的每一条边 e_ii包含两个权值 a_i与 b_i 。
若身上携带的 A 型守护精灵个数不少于 a_i? ，且 B 型守护精灵个数不少于 b_i ，这条边上的妖怪就不会对通过这条边的人发起攻击。
当且仅当通过这片魔法森林的过程中没有任意一条边的妖怪向 小 E 发起攻击，他才能成功找到隐士。
由于携带守护精灵是一件非常麻烦的事，小 E 想要知道，要能够成功拜访到 隐士，最少需要携带守护精灵的总个数。
守护精灵的总个数为 A 型守护精灵的个数与 B 型守护精灵的个数之和。
输入格式
输入文件的第 1行包含两个整数 n,m，表示无向图共有 n 个节点，m 条边。 接下来 m 行，第 i+1 行包含 4 个正整数 X_i,Y_i,a_i,b_i，
描述第 i 条无向边。 其中 X_i与 Y_i为该边两个端点的标号，a_i? 与 b_i? 的含义如题所述。 注意数据中可能包含重边与自环。
输出格式
输出一行一个整数：如果小 E 可以成功拜访到隐士，输出小 E 最少需要携 带的守护精灵的总个数；如果无论如何小 E 都无法拜访到隐士，输出 -1。
Solution
发现这道题可以用最小生成树的思想
将所有边按a从小到大排序，再按最小生成树加入图中，则此时1~n的最大a必定最小
出现环时找到环中b最大的一条边删去
那么我们需要一种可以动态加边删边和查询路径中最大b的数据结构，那就是LCT了
注意要把边和两端点都看成点，才能方便地删除和连边
Code
#include <cstdio> #include <cstdlib> #include <algorithm> using namespace std; const int N=15e4+10; int fa[N],top[N],val[N],ch[N][2],rev[N],sum[N]; int n,m,ans=2e9; struct node { int x,y,a,b; bool operator <(const node &o)const { return a<o.a; } }d[N]; inline char get() { static char buf[1024]; static int pos=0,size=0; if(pos==size) { size=fread(buf,1,1024,stdin); pos=0; if(!size) return EOF; else return buf[pos++]; } else return buf[pos++]; } int read() { int sum=0,fh=1; char ch=get(); while(!(ch>=‘0‘ && ch<=‘9‘)) { if(ch==‘-‘) fh=-1; ch=get(); } while(ch>=‘0‘ && ch<=‘9‘ && ch!=EOF) sum=sum*10+ch-48,ch=get(); return sum*fh; } void push_up(int x) { sum[x]=x; if(ch[x][0] && val[sum[ch[x][0]]]>val[sum[x]]) sum[x]=sum[ch[x][0]]; if(ch[x][1] && val[sum[ch[x][1]]]>val[sum[x]]) sum[x]=sum[ch[x][1]]; } bool nroot(int x) { return x==ch[fa[x]][0] || x==ch[fa[x]][1]; } int get(int x) { return x==ch[fa[x]][1]; } void change(int x) { if(!x) return ; swap(ch[x][0],ch[x][1]); rev[x]^=1; } void push_down(int x) { if(rev[x]) { change(ch[x][0]); change(ch[x][1]); rev[x]=0; } } void dfs(int x) { if(nroot(x)) dfs(fa[x]); push_down(x); } void rotate(int x) { int y=fa[x],z=fa[y],wh=get(x); if(nroot(y)) ch[z][get(y)]=x; if(ch[x][wh^1]) fa[ch[x][wh^1]]=y; ch[y][wh]=ch[x][wh^1]; ch[x][wh^1]=y; fa[y]=x,fa[x]=z; push_up(y),push_up(x); } void splay(int x) { dfs(x); for(int fx;fx=fa[x],nroot(x);rotate(x)) if(nroot(fx)) rotate(get(x)==get(fx)?fx:x); } void access(int x) { for(int y=0;x;x=fa[y=x]) splay(x),ch[x][1]=y,push_up(x); } void makeroot(int x) { access(x),splay(x); change(x); } int findroot(int x) { access(x),splay(x); while(ch[x][0]) push_down(x),x=ch[x][0]; splay(x); return x; } void link(int x,int y) { makeroot(x); if(findroot(y)!=x) fa[x]=y; } void cut(int x,int y) { makeroot(x); if(findroot(y)==x && fa[y]==x && !ch[y][0]) fa[y]=ch[x][1]=0; } int split(int x,int y) { makeroot(x); access(y); splay(y); return sum[y]; } int get_top(int x) { return x==top[x]?x:top[x]=get_top(top[x]); } int main() { n=read(),m=read(); for(int i=1;i<=m;i++) d[i]=(node){read(),read(),read(),read()}; sort(d+1,d+1+m); for(int i=1;i<=n+m;i++) top[i]=sum[i]=i; for(int i=1;i<=m;i++) val[i+n]=d[i].b; for(int i=1;i<=m;i++) { int fx=get_top(d[i].x),fy=get_top(d[i].y); bool flag=true; if(fx==fy) { int w=split(d[i].x,d[i].y); if(val[w]>d[i].b) cut(d[w-n].x,w),cut(w,d[w-n].y); else flag=false; } else top[fx]=fy; if(flag) link(d[i].x,i+n),link(i+n,d[i].y); if(get_top(1)==get_top(n)) ans=min(ans,d[i].a+val[split(1,n)]); } if(ans<2e9) printf("%d\n",ans); else puts("-1"); return 0; }
原文：https://www.cnblogs.com/hsez-cyx/p/12289762.html