「BZOJ1715」[Usaco2006 Dec] Wormholes 虫洞
Description
John在他的农场中闲逛时发现了许多虫洞。虫洞可以看作一条十分奇特的有向边，并可以使你返回到过去的一个时刻（相对你进入虫洞之前）。John的每个农场有M条小路（无向边)连接着N （从1..N标号）块地，并有W个虫洞。其中1<=N<=500,1<=M<=2500,1<=W<=200。 现在John想借助这些虫洞来回到过去（出发时刻之前），请你告诉他能办到吗。 John将向你提供F(1<=F<=5)个农场的地图。没有小路会耗费你超过10000秒的时间，当然也没有虫洞回帮你回到超过10000秒以前。
Input
* Line 1: 一个整数 F, 表示农场个数。
* Line 1 of each farm: 三个整数 N, M, W。
* Lines 2..M+1 of each farm: 三个数（S, E, T）。表示在标号为S的地与标号为E的地中间有一条用时T秒的小路。
* Lines M+2..M+W+1 of each farm: 三个数（S, E, T）。表示在标号为S的地与标号为E的地中间有一条可以使John到达T秒前的虫洞。
Output
* Lines 1..F: 如果John能在这个农场实现他的目标，输出”YES”,否则输出”NO”。
Sample Input
2
3 3 1
1 2 2
1 3 4
2 3 1
3 1 3
3 2 1
1 2 3
2 3 4
3 1 8
3 3 1
1 2 2
1 3 4
2 3 1
3 1 3
3 2 1
1 2 3
2 3 4
3 1 8
Sample Output
NO
YES
YES
题解
本题就是问图中是否存在负环
找负环很多方法，spfa入队次数>n什么的
不过我一般写dfs版的spfa，据说比较快。。。
就是dfs一个点，如果从它dfs出去的点能够返回来更新它的话
说明构成了负环
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 |
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> #define ll long long #define inf 0x7ffffff using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int F,n,m,W,cnt; int head[505],dis[505]; bool flag,mark[505]; struct data{int to,next,v;}e[100001]; void ins(int u,int v,int w) {e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;e[cnt].v=w;} void insert(int u,int v,int w) {ins(u,v,w);ins(v,u,w);} void spfa(int x) { mark[x]=1; for(int i=head[x];i;i=e[i].next) if(e[i].v+dis[x]<dis[e[i].to]) { if(mark[e[i].to]){flag=1;return;} else { dis[e[i].to]=e[i].v+dis[x]; spfa(e[i].to); } } mark[x]=0; } bool jud() { for(int i=1;i<=n;i++){dis[i]=mark[i]=0;} flag=0; for(int i=1;i<=n;i++) {spfa(i);if(flag)return 1;} return 0; } int main() { F=read(); while(F--) { cnt=0; memset(head,0,sizeof(head)); n=read(),m=read(),W=read(); int u,v,w; for(int i=1;i<=m;i++) u=read(),v=read(),w=read(),insert(u,v,w); for(int i=1;i<=W;i++) u=read(),v=read(),w=read(),ins(u,v,-w); if(jud())printf("YES\n"); else printf("NO\n"); } return 0; } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 |
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> #define ll long long #define inf 0x7ffffff using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int F,n,m,W,cnt; int head[505],dis[505]; bool flag,mark[505]; struct data{int to,next,v;}e[100001]; void ins(int u,int v,int w) {e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;e[cnt].v=w;} void insert(int u,int v,int w) {ins(u,v,w);ins(v,u,w);} void spfa(int x) { mark[x]=1; for(int i=head[x];i;i=e[i].next) if(e[i].v+dis[x]<dis[e[i].to]) { if(mark[e[i].to]){flag=1;return;} else { dis[e[i].to]=e[i].v+dis[x]; spfa(e[i].to); } } mark[x]=0; } bool jud() { for(int i=1;i<=n;i++){dis[i]=inf;mark[i]=0;} flag=0; for(int i=1;i<=n;i++) {dis[i]=0;spfa(i);if(flag)return 1;} return 0; } int main() { F=read(); while(F--) { cnt=0; memset(head,0,sizeof(head)); n=read(),m=read(),W=read(); int u,v,w; for(int i=1;i<=m;i++) u=read(),v=read(),w=read(),insert(u,v,w); for(int i=1;i<=W;i++) u=read(),v=read(),w=read(),ins(u,v,-w); if(jud())printf("YES\n"); else printf("NO\n"); } return 0; } |
Subscribe
计数器 9854367
OI 课件=>
OI 课件=>