为了得到书法大家的真传，小 E 同学下定决心去拜访住在魔法森林中的隐 士。魔法森林可以被看成一个包含 \(n\) 个节点 \(m\) 条边的无向图，节点标号为 \(1,2,3,…,n\)，边标号为 \(1,2,3,…,m\)。初始时小 E 同学在 \(1\) 号节点，隐士则住在 \(n\) 号节点。小 E 需要通过这一片魔法森林，才能够拜访到隐士。
魔法森林中居住了一些妖怪。每当有人经过一条边的时候，这条边上的妖怪 就会对其发起攻击。幸运的是，在 \(1\) 号节点住着两种守护精灵：A 型守护精灵与 B 型守护精灵。小 E 可以借助它们的力量，达到自己的目的。
只要小 E 带上足够多的守护精灵，妖怪们就不会发起攻击了。具体来说，无 向图中的每一条边 \(e_i\) 包含两个权值 \(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 。
动态树求解动态最小生成树
从小到大枚举A型守护精灵的个数，很显然A的值只会等于\(a_i\)中的一个。
当A的值确定之后，原图中的\(a_i\)大于A的值的边都会被删去，随着A的值的不断增大，会不断有边加入。
使用动态树维护生成树两个节点之间\(b_i\)的最大值，那么每当一条新的边加入生成树时，我们可以求出这条新边两个端点之前原来的\(b_i\)的最大值，如果这个最大值比\(b_i\)大，那么找到这条\(b_i\)最大的边并把它从生成树中删除，动态树中断开，并把新边加入，操作时算一下最小值最后输出就行了。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAXN 200010
struct Node{
int u,v,a,b;
Node(){}
Node(int u,int v,int a,int b):u(u),v(v),a(a),b(b){}
bool operator < (const Node &aa) const{
return a<aa.a;
}
}p[MAXN];
int ch[MAXN][2],fa[MAXN],maxid[MAXN],q[MAXN],linkline[MAXN][2],val[MAXN];
bool rev[MAXN];
int i,j,k,m,n,x,y,u,v,a,b,qtop,ans,ncnt;
char readc;
void read(int &n){
while((readc=getchar())<48||readc>57);
n=readc-48;
while((readc=getchar())>=48&&readc<=57) n=n*10+readc-48;
}
int get(int x){
return ch[fa[x]][1]==x;
}
bool isroot(int x){
return ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x;
}
void pushup(int x){
int tmp=x;
if(val[tmp]<val[maxid[ch[x][0]]]) tmp=maxid[ch[x][0]];
if(val[tmp]<val[maxid[ch[x][1]]]) tmp=maxid[ch[x][1]];
maxid[x]=tmp;
}
void pushdown(int x){
if(rev[x]){
swap(ch[x][0],ch[x][1]);
rev[ch[x][0]]^=1,rev[ch[x][1]]^=1;
rev[x]=false;
}
}
void rotate(int x){
int y=fa[x],z=fa[y],k=get(x),w=ch[x][k^1];
ch[y][k]=w,fa[w]=y;
if(!isroot(y)) ch[z][get(y)]=x;
fa[x]=z;
ch[x][k^1]=y,fa[y]=x;
pushup(y),pushup(x);
}
void splay(int x){
q[qtop=1]=x;
for(int i=x;!isroot(i);i=fa[i]) q[++qtop]=fa[i];
for(int i=qtop;i>=1;i--) pushdown(q[i]);
while(!isroot(x)){
int y=fa[x];
if(!isroot(y)){
if(get(x)==get(y)) rotate(y); else rotate(x);
}
rotate(x);
}
pushup(x);
}
void access(int x){
for(int y=0;x;y=x,x=fa[x]){
splay(x),ch[x][1]=y;
pushup(x);
}
}
void makeroot(int x){
access(x);
splay(x);
rev[x]^=1;
}
void split(int x,int y){
makeroot(x);
access(y);
splay(y);
}
int findroot(int x){
access(x);
splay(x);
while(ch[x][0]) pushdown(x),x=ch[x][0];
return x;
}
void link(int x,int y){
makeroot(x);
if(findroot(y)!=x) fa[x]=y;
}
void cut(int x,int y){
split(x,y);
if(findroot(y)==x&&fa[x]==y&&ch[x][1]==0){
fa[x]=0;
ch[y][0]=0;
pushup(y);
}
}
void update(int id){
int x=p[id].u,y=p[id].v;
if(x==y) return;
makeroot(x);
if(findroot(y)!=x){
val[++ncnt]=p[id].b;
link(x,ncnt);
linkline[ncnt][0]=x;
link(y,ncnt);
linkline[ncnt][1]=y;
}else{
split(x,y);
int tmp=maxid[y];
if(p[id].b<val[tmp]){
cut(linkline[tmp][0],tmp);
cut(linkline[tmp][1],tmp);
val[tmp]=p[id].b;
link(x,tmp);
link(y,tmp);
linkline[tmp][0]=x,linkline[tmp][1]=y;
}
}
}
int query(){
if(findroot(1)!=findroot(n)) return 1000000000;
split(1,n);
return val[maxid[n]];
}
int main(){
ans=1000000000;
read(n),read(m);
for(i=1;i<=m;i++){
read(x),read(y),read(a),read(b);
if(x>y) swap(x,y);
p[i]=Node(x,y,a,b);
}
ncnt=n;
sort(p+1,p+m+1);
for(i=1;i<=m;i++){
update(i);
ans=min(ans,query()+p[i].a);
}
if(ans==1000000000){
printf("-1\n");
}else{
printf("%d\n",ans);
}
return 0;
}原文：https://www.cnblogs.com/linxif2008/p/10347382.html