首页 > 代码库 > BZOJ 1715: [Usaco2006 Dec]Wormholes 虫洞

BZOJ 1715: [Usaco2006 Dec]Wormholes 虫洞

题目

1715: [Usaco2006 Dec]Wormholes 虫洞

Time Limit: 5 Sec  Memory Limit: 64 MB

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

Sample Output

NO
YES

题解

SPFA的负权回路判断,就是一个点被松弛了n次以上,那么这张图存在一个负权回路!Orz看到hzwer大神用DFS写了一个判断负权回路比我快了整整5倍,我就被吓哭了!也讲一下DFS的版本吧,就是如果存在一个点,从它DFS出去的点反过来更新他自己,那么这个图就存在负权回路QAQ

代码

 1 /*Author:WNJXYK*/ 2 #include<cstdio> 3 #include<cstring> 4 #include<queue> 5 using namespace std; 6 int T; 7 int n,m,w; 8 struct Edge{ 9     int v;10     int t;11     int nxt;12     Edge(){}13     Edge(int a,int b,int c){14         v=a;t=b;nxt=c;15     }16 };17 Edge e[6000];18 int nume;19 int head[510];20 21 inline void addSingleEdge(int x,int y,int w){22     e[++nume]=Edge(y,w,head[x]);23     head[x]=nume;24 }25 inline void addEdge(int x,int y,int w){26     addSingleEdge(x,y,w);27     addSingleEdge(y,x,w);28 }29 30 queue<int> que;31 int dist[510];32 bool inque[510];33 int intime[510];34 35 inline void solve(){36     bool isPrint=false;37     while(!que.empty()) que.pop();38     memset(dist,127/3,sizeof(dist));39     memset(inque,false,sizeof(inque));40     memset(intime,0,sizeof(intime));41     que.push(1);42     dist[1]=0;43     inque[1]=true;44     intime[1]++;45     while(!que.empty()){46         int now=que.front();47         que.pop();48         for (int i=head[now];i;i=e[i].nxt){49             int v=e[i].v;int w=e[i].t;50             if (dist[v]>dist[now]+w){51                 intime[v]++;52                 if (intime[v]>n){53                     printf("YES\n");54                     isPrint=true;55                     break;56                 }57                 dist[v]=dist[now]+w;58                 if (!inque[v]){59                     inque[v]=true;60                     que.push(v);61                 }62             }63         }64         if (isPrint) break;65         inque[now]=false;66     }67     if (isPrint==false) printf("NO\n");68 }69 inline void read(){70     scanf("%d%d%d",&n,&m,&w);71     memset(head,0,sizeof(head));72     nume=0;73     for (int i=1;i<=m;i++){74         int x,y,t;75         scanf("%d%d%d",&x,&y,&t);76         addEdge(x,y,t);77     }78     for (int i=1;i<=w;i++){79         int x,y,t;80         scanf("%d%d%d",&x,&y,&t);81         addSingleEdge(x,y,-t);82     }83 }84 85 int main(){86     scanf("%d",&T);87     for (;T--;){88         read();89         solve();90     }91     return 0;92 }
View Code

hzwer大神的DFS版 http://hzwer.com/3189.html 

BZOJ 1715: [Usaco2006 Dec]Wormholes 虫洞