题目描述
为了得到书法大家的真传，小 E 同学下定决心去拜访住在魔法森林中的隐 士。魔法森林可以被看成一个包含 n 个节点 m 条边的无向图，节点标号为 1,2,3,…,n，边标号为 1,2,3,…,m。初始时小 E 同学在 1 号节点，隐士则住在 n 号节点。小 E 需要通过这一片魔法森林，才能够拜访到隐士。
魔法森林中居住了一些妖怪。每当有人经过一条边的时候，这条边上的妖怪 就会对其发起攻击。幸运的是，在 1 号节点住着两种守护精灵：A 型守护精灵与 B 型守护精灵。小 E 可以借助它们的力量，达到自己的目的。
只要小 E 带上足够多的守护精灵，妖怪们就不会发起攻击了。具体来说，无 向图中的每一条边 ei 包含两个权值 ai 与 bi 。若身上携带的 A 型守护精灵个数不 少于 ai ，且 B 型守护精灵个数不少于 bi ，这条边上的妖怪就不会对通过这条边 的人发起攻击。当且仅当通过这片魔法森林的过程中没有任意一条边的妖怪向 小 E 发起攻击，他才能成功找到隐士。
由于携带守护精灵是一件非常麻烦的事，小 E 想要知道，要能够成功拜访到 隐士，最少需要携带守护精灵的总个数。守护精灵的总个数为 A 型守护精灵的 个数与 B 型守护精灵的个数之和。
输入输出格式
输入格式：
输入文件的第 1 行包含两个整数 n,m，表示无向图共有 n 个节点，m 条边。 接下来 m 行，第i+ 1 行包含 4 个正整数 Xi,Yi,ai,bi，描述第i条无向边。 其中Xi与 Yi为该边两个端点的标号，ai 与 bi 的含义如题所述。 注意数据中可能包含重边与自环。
输出格式：
输出一行一个整数：如果小 E 可以成功拜访到隐士，输出小 E 最少需要携 带的守护精灵的总个数；如果无论如何小 E 都无法拜访到隐士，输出“-1”（不 含引号）。
输入输出样例
说明
* 解释1
如果小 E 走路径 1→2→4，需要携带 19+15=34 个守护精灵； 如果小 E 走路径 1→3→4，需要携带 17+17=34 个守护精灵； 如果小 E 走路径 1→2→3→4，需要携带 19+17=36 个守护精灵； 如果小 E 走路径 1→3→2→4，需要携带 17+15=32 个守护精灵。 综上所述，小 E 最少需要携带 32 个守护精灵。
* 解释2
小 E 无法从 1 号节点到达 3 号节点，故输出-1。
题解：思考一下其实和最小差值生成树的玩法有点像，我们可以先把a排下序，逐渐往里面加，维护b的动态最小生成树，显然此时的b是对于当前a最小的，如果此时1与n联通，用a+b更新ans就可以了，显然答案在加边的过程中一定搞得出来
代码如下：
#include<map> #include<set> #include<queue> #include<cmath> #include<cstdio> #include<string> #include<vector> #include<cstring> #include<iostream> #include<algorithm> #define lson ch[x][0] #define rson ch[x][1] using namespace std; int n,m,f[200020],ch[200020][2],tag[200020],w[200020],sum[200020]; struct node { int from,to,a,b; } e[200020]; int cmp(node a,node b) { return a.a<b.a; } int not_root(int now) { int x=f[now]; return lson==now||rson==now; } int push_up(int x) { sum[x]=x; if(e[sum[x]].b<e[sum[lson]].b) { sum[x]=sum[lson]; } if(e[sum[x]].b<e[sum[rson]].b) { sum[x]=sum[rson]; } } int rev(int x) { swap(lson,rson); tag[x]^=1; } int push_down(int x) { if(tag[x]) { rev(lson); rev(rson); tag[x]^=1; } } int rotate(int x) { int y=f[x],z=f[y],kd=ch[y][1]==x,xs=ch[x][!kd]; if(not_root(y)) ch[z][ch[z][1]==y]=x; ch[x][!kd]=y; ch[y][kd]=xs; if(xs) f[xs]=y; f[y]=x; f[x]=z; push_up(y); } int push_all(int x) { if(not_root(x)) { push_all(f[x]); } push_down(x); } int splay(int x) { int y,z; push_all(x); while(not_root(x)) { y=f[x],z=f[y]; if(not_root(y)) { (ch[y][1]==x)^(ch[z][1]==y)?rotate(x):rotate(y); } rotate(x); } push_up(x); } int access(int x) { int y; for(y=0; x; y=x,x=f[x]) { splay(x); rson=y; push_up(x); } } int make_root(int x) { access(x); splay(x); rev(x); } int split(int x,int y) { make_root(x); access(y); splay(y); } int find_root(int x) { access(x); splay(x); while(lson) { push_down(x); x=lson; } return x; } int link(int x,int y) { make_root(x); if(find_root(y)==x) return 0; f[x]=y; return 1; } int cut(int x,int y) { make_root(x); if(find_root(y)!=x||f[x]!=y||rson) return 0; f[x]=ch[y][0]=0; push_up(y); return 1; } int main() { scanf("%d%d",&n,&m); for(int i=1; i<=m; i++) { scanf("%d%d%d%d",&e[i].from,&e[i].to,&e[i].a,&e[i].b); } sort(e+1,e+m+1,cmp); int ans=0x3f3f3f3f; for(int i=1; i<=m; i++) { make_root(e[i].from+m); if(find_root(e[i].to+m)==e[i].from+m) { split(e[i].from+m,e[i].to+m); int tmp=sum[e[i].to+m]; if(e[tmp].b>e[i].b) { cut(e[tmp].to+m,tmp); cut(e[tmp].from+m,tmp); link(e[i].from+m,i); link(e[i].to+m,i); } } else { link(e[i].from+m,i); link(e[i].to+m,i); } make_root(1+m); if(find_root(n+m)==1+m) ans=min(ans,e[i].a+e[sum[n+m]].b); } if(ans<0x3f3f3f3f) printf("%d ",ans); else puts("-1"); }