3669: [Noi2014]魔法森林
Time Limit: 30 Sec Memory Limit: 512 MB
- Submit: 3553 Solved: 2278
- [Submit https://www.lydsy.com/JudgeOnline/submitpage.php?id=3669 ][Status https://www.lydsy.com/JudgeOnline/problemstatus.php?id=3669 ][Discuss https://www.lydsy.com/JudgeOnline/bbs.php?id=3669 ]
- Description
为了得到书法大家的真传, 小 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 型守护精灵的个数之和.
Input
第 1 行包含两个整数 N,M, 表示无向图共有 N 个节点, M 条边. 接下来 M 行, 第行包含 4 个正整数 Xi,Yi,Ai,Bi, 描述第 i 条无向边. 其中 Xi 与 Yi 为该边两个端点的标号, Ai 与 Bi 的含义如题所述. 注意数据中可能包含重边与自环.
Output
输出一行一个整数: 如果小 E 可以成功拜访到隐士, 输出小 E 最少需要携带的守护精灵的总个数; 如果无论如何小 E 都无法拜访到隐士, 输出 "-1"(不含引号).
Sample Input
[输入样例 1]
- 4 5
- 1 2 19 1
- 2 3 8 12
- 2 4 12 15
- 1 3 17 8
- 3 4 1 17
[输入样例 2]
- 3 1
- 1 2 1 1
- Sample Output
[输出样例 1]
32
[样例说明 1]
如果小 E 走路径 124, 需要携带 19+15=34 个守护精灵;
如果小 E 走路径 134, 需要携带 17+17=34 个守护精灵;
如果小 E 走路径 1234, 需要携带 19+17=36 个守护精灵;
如果小 E 走路径 1324, 需要携带 17+15=32 个守护精灵.
综上所述, 小 E 最少需要携带 32 个守护精灵.
[输出样例 2]
-1
[样例说明 2]
小 E 无法从 1 号节点到达 3 号节点, 故输出 - 1.
- HINT
- 2<=n<=50,000
- 0<=m<=100,000
- 1<=ai ,bi<=50,000
出来集训没带电脑, 只能蹭雅礼的机房了, 我愉快 (傻逼) 的敲了调了两个小时, 一直有 4 个点是 RE
并且我发现那四个点的 ai 都很小, 我以为大数据都过了, 小数据不可能会卡, 一直以为自己是对的, 后来眼睛一斜, 貌似发现了 sort 的 cmp 函数如果带等号的话不能对有重复的元素进行排序
否则会 RE
好了, 还说一下这道题的做法, 很裸地就是直接 kruskal, 再在环上删边 我们发现可以对此进行优化, 有 lct 去维护最大值, 当出现环的时候, 就删除并连边
- #include <bits/stdc++.h>
- #define ll long long
- #define inf 1e9+10
- using namespace std;
- inline int read(){
- int x=0;int f=1;char ch=getchar();
- while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
- while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
- return x*f;
- }
- const int MAXN=1e6+10;
- struct node{
- int x,y,a,b;
- }e[MAXN];
- inline bool cmp(node n,node m){
- return n.a<m.a;
- }
- struct Tree{
- int maxid,mx,son[2],fa,tag,val;
- }T[MAXN];
- int n,q[MAXN],top,ans,f[MAXN],m;
- inline int find(int x){
- return x==f[x]?x:f[x]=find(f[x]);
- }
- inline int isroot(int x){
- if(!T[x].fa) return 1;
- return T[T[x].fa].son[0]!=x&&T[T[x].fa].son[1]!=x;
- }
- inline void downit(int x){
- if(T[x].tag){
- if(T[x].son[0]) T[T[x].son[0]].tag^=1;
- if(T[x].son[1]) T[T[x].son[1]].tag^=1;
- T[x].tag=0;swap(T[x].son[0],T[x].son[1]);
- }
- }
- inline void update(int x){
- int l=T[x].son[0];int r=T[x].son[1];T[x].mx=T[x].val;T[x].maxid=x;
- if(l){
- if(T[l].mx>T[x].mx) T[x].mx=T[l].mx,T[x].maxid=T[l].maxid;
- }
- if(r){
- if(T[r].mx>T[x].mx) T[x].mx=T[r].mx,T[x].maxid=T[r].maxid;
- }
- }
- inline int get(int x){
- return x==T[T[x].fa].son[1];
- }
- inline void rotate(int x){
- int old=T[x].fa,oldf=T[old].fa,which=get(x);
- if(!isroot(old)) T[oldf].son[get(old)]=x;
- T[old].son[which]=T[x].son[which^1];T[T[x].son[which^1]].fa=old;
- T[x].son[which^1]=old;T[old].fa=x;T[x].fa=oldf;
- update(old);update(x);
- }
- inline void splay(int x){
- top=0;q[++top]=x;
- for(int i=x;i;i=T[i].fa) q[++top]=T[i].fa;
- for(int i=top;i>=1;i--) downit(q[i]);
- while(!isroot(x)){
- int old=T[x].fa;
- if(!isroot(old)){
- if(get(old)==get(x)) rotate(old);
- else rotate(x);
- }
- rotate(x);
- }
- }
- inline void access(int x){
- int t=0;
- while(x){
- splay(x);T[x].son[1]=t;update(x);t=x;x=T[x].fa;
- }
- }
- inline void Reverse(int x){
- access(x);splay(x);T[x].tag^=1;
- }
- inline void cnt(int x,int y){
- Reverse(x);access(y);splay(y);T[y].son[0]=T[x].fa=0;update(y);
- }
- inline void linkk(int x,int y){
- Reverse(x);T[x].fa=y;
- }
- inline int query(int x,int y){
- Reverse(x);access(y);splay(y);
- return T[y].maxid;
- }
- int main(){
- //freopen("All.in","r",stdin);
- //freopen("zem.out","w",stdout);
- n=read();m=read();
- for(int i=1;i<=n;i++) f[i]=i;
- for(int i=1;i<=m;i++){
- e[i].x=read();e[i].y=read();e[i].a=read();e[i].b=read();
- }
- sort(e+1,e+m+1,cmp);ans=inf;
- for(int i=1;i<=m;i++){
- int x=e[i].x;int y=e[i].y;
- if(find(x)==find(y)){
- int t=query(x,y);
- if(e[i].b<T[t].val){
- cnt(t,e[t-n].x);cnt(t,e[t-n].y);
- }
- else{
- if(find(1)==find(n)) ans=min(ans,T[query(1,n)].val+e[i].a);
- continue;
- }
- }
- else f[find(x)]=find(y);
- T[n+i].mx=T[n+i].val=e[i].b;T[n+i].maxid=n+i;
- linkk(x,n+i);linkk(y,n+i);
- if(find(1)==find(n)) ans=min(ans,T[query(1,n)].val+e[i].a);
- }
- if(ans==inf) printf("-1\n");
- else printf("%d\n",ans);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2666024.html