bzoj 3669 魔法森林

news/2024/10/30 9:27:39/

3669: [Noi2014]魔法森林

Time Limit: 30 Sec   Memory Limit: 512 MB
Submit: 2690   Solved: 1667
[ Submit][ Status][ Discuss]

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走路径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】


-1
【样例说明2】
小E无法从1号节点到达3号节点,故输出-1。

HINT

2<=n<=50,000


0<=m<=100,000




1<=ai ,bi<=50,000

Source



【分析】

Wc 水管 的水化水化版...



【代码】

//NOI 2014 膜法森林
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#define ll long long
#define fo(i,j,k) for(i=j;i<=k;i++)
using namespace std;
const int mxn=200005;
int n,m,top,ans=1e9+7;
struct edge {int l,r,a,b;} e[mxn];
int f[mxn],ch[mxn][2],rev[mxn],st[mxn],mx[mxn],val[mxn];
inline bool comp(edge x,edge y) {return x.a==y.a?x.b<y.b:x.a<y.a;}
inline bool isroot(int x) {return ch[f[x]][0]!=x && ch[f[x]][1]!=x;}
inline int get(int x) {return ch[f[x]][1]==x;}
inline void update(int x)
{mx[x]=x;int l=ch[x][0],r=ch[x][1];if(val[mx[l]]>val[mx[x]]) mx[x]=mx[l];if(val[mx[r]]>val[mx[x]]) mx[x]=mx[r];
}
inline void reverse(int x) {if(!x) return;rev[x]^=1,swap(ch[x][0],ch[x][1]);}
inline void pushdown(int x) {if(rev[x]) reverse(ch[x][0]),reverse(ch[x][1]),rev[x]=0;}
inline void rotate(int x)
{pushdown(x);int fa=f[x],fafa=f[fa],which=get(x);if(!isroot(fa)) ch[fafa][ch[fafa][1]==fa]=x;f[x]=fafa;ch[fa][which]=ch[x][which^1],f[ch[fa][which]]=fa;ch[x][which^1]=fa,f[fa]=x;update(fa),update(x);
}
inline void splay(int x)
{st[top=1]=x;for(int i=x;!isroot(i);i=f[i]) st[++top]=f[i];for(int i=top;i;i--) pushdown(st[i]);for(int fa;!isroot(x);rotate(x))if(!isroot(fa=f[x])) rotate(get(x)==get(fa)?fa:x);
}
inline void access(int x) {for(int y=0;x;y=x,x=f[x]) splay(x),ch[x][1]=y,update(x);}
inline void makeroot(int x) {access(x),splay(x),reverse(x);}
inline int find(int x) {access(x),splay(x);while(ch[x][0]) x=ch[x][0];return x;}
inline void split(int x,int y) {makeroot(x),access(y),splay(y);}
inline void link(int x,int y) {makeroot(x),f[x]=y;}
inline void cut(int x,int y) {split(x,y),ch[y][0]=f[x]=0;}
int main()
{int i,j;scanf("%d%d",&n,&m);fo(i,1,m) scanf("%d%d%d%d",&e[i].l,&e[i].r,&e[i].a,&e[i].b);sort(e+1,e+m+1,comp);fo(i,1,m) {val[i+n]=e[i].b;int u=e[i].l,v=e[i].r;if(find(u)!=find(v))link(i+n,u),link(i+n,v);else{split(u,v);int tmp=mx[v];  //u->v路径最大权节点if(val[i+n]<val[tmp]){cut(tmp,e[tmp-n].l),cut(tmp,e[tmp-n].r);link(i+n,u),link(i+n,v);}}if(find(1)==find(n)) split(1,n),ans=min(ans,e[i].a+val[mx[n]]);}printf("%d\n",ans==1e9+7?-1:ans);return 0;
}



http://www.ppmy.cn/news/131391.html

相关文章

poj3669 bfs

流星雨来袭击我们的女主牛了&#xff0c;Bessie。为了找一个安全地方&#xff0c;她开始逃了。地图相当于平面坐标系第一象限&#xff0c;Bessie一开始在原点。然后&#xff0c;每颗流星都会在某个时刻砸下来&#xff0c;砸到的地方连同上下左右都会被毁灭&#xff0c;此时这些…

【题解】POJ 3669 Meteor Shower(BFS)

POJ 3669 Meteor Shower https://vjudge.net/problem/POJ-3669 题意 有一场流星雨即将到来&#xff0c;Bessie要找到一个安全的地方。现在已知有M颗流星&#xff0c;并且知道它们抵达的位置和时间&#xff0c;Bessi走一个单位需要一个单位时间&#xff0c;问到达安全位置的最短…

poj3669

题意&#xff1a;巨大流星雨即将袭来。每个流星会对击中的地方以及周围&#xff08;上下左右四格&#xff09;造成破坏。Bessie开始时位于&#xff08;0, 0&#xff09;位置&#xff0c;并希望逃到一处不会被袭击到的地方&#xff08;在第一象限内&#xff09;。已知每移动一格…

bzoj3669

对于这道题的解法&#xff0c;感觉是部分暴力&#xff0c;枚举带几只A型守护精灵&#xff0c;就可以将这道题转化成求类似于bzoj2594了。 参考题解&#xff1a; http://wenku.baidu.com/view/a611cec4dd3383c4bb4cd2d8.html http://www.cnblogs.com/JoeFan/p/4451249.html 找错…

poj 3669

bfs的题 因为每次都模拟流行砸下来&#xff0c;tle一次&#xff0c;&#xff08;应该标记每个点被砸的时间&#xff09; 因为没有标记走过的点不能再走&#xff0c;tle了一次&#xff0c;&#xff08;之前认为走过的点应该可以再走&#xff0c;其实仔细想的话&#xff0c;走过的…

ORACLE ASM常用命令整理

ASM 命令整理 一. 查看ASM空间使用情况 1. lsdg: 查看磁盘组的信息&#xff0c;和磁盘空间大小 ASMCMD> lsdg State Type Rebal Block AU Total_MB Free_MB Usable_file_MB Offline_disks Voting_files Name MOUNTED EXTERN N 4096 1048576 …

POJ-3669广度优先搜索

这是一道典型的广度优先搜索BFS题目。 首先声明一下&#xff0c;我在这里借鉴了别人的想法&#xff1a;这是原文答案&#xff0c;请点击 题目大意&#xff1a; 流星雨即将攻击地球&#xff0c;当然数目是有限的&#xff0c;共n个&#xff0c;攻击到某个点时将会使该点及其上…

POJ 3669(优先队列BFS)(对地图进行优化)

题目新颖&#xff0c;解法也是比较难想的。 题目&#xff1a; Bessie听说有场史无前例的流星雨即将来临&#xff1b;有谶言&#xff1a;陨星将落&#xff0c;徒留灰烬。为保生机&#xff0c;她誓将找寻安全之所&#xff08;永避星坠之地&#xff09;。目前她正在平面坐标系的…