解题报告：poj 3259 Wormholes（入门spfa判断负环）

Description

While exploring his many farms, Farmer John has discovered a number of amazing wormholes. A wormhole is very peculiar because it is a one-way path that delivers you to its destination at a time that is BEFORE you entered the wormhole! Each of FJ's farms comprises N (1 ≤ N ≤ 500) fields conveniently numbered 1..N, M (1 ≤ M ≤ 2500) paths, and W (1 ≤ W≤ 200) wormholes.

As FJ is an avid time-traveling fan, he wants to do the following: start at some field, travel through some paths and wormholes, and return to the starting field a time before his initial departure. Perhaps he will be able to meet himself :) .

To help FJ find out whether this is possible or not, he will supply you with complete maps to F (1 ≤ F ≤ 5) of his farms. No paths will take longer than 10,000 seconds to travel and no wormhole can bring FJ back in time by more than 10,000 seconds.

Input

Line 1: A single integer, F. F farm descriptions follow.
Line 1 of each farm: Three space-separated integers respectively: N, M, and W
Lines 2..M+1 of each farm: Three space-separated numbers (S, E, T) that describe, respectively: a bidirectional path between S and E that requires T seconds to traverse. Two fields might be connected by more than one path.
Lines M+2..M+W+1 of each farm: Three space-separated numbers (S, E, T) that describe, respectively: A one way path from S to E that also moves the traveler back T seconds.

Output

Lines 1..F: For each farm, output "YES" if FJ can achieve his goal, otherwise output "NO" (do not include the quotes).

Sample Input

Sample Output

NO

YES

Hint

For farm 1, FJ cannot travel back in time.
For farm 2, FJ could travel back in time by the cycle 1->2->3->1, arriving back at his starting location 1 second before he leaves. He could start from anywhere on the cycle to accomplish this.

解题思路：本题可用floyd或者spfa算法来判断是否有负环。题意：有f个农场，每个农场有n块地，其间有m条路，w条虫洞，穿过虫洞之后相应的时间会倒退t秒，问是否可以从某块地出发到达另一块地之后通过虫洞逆流时间回到当初出发的那个时间点。怎么建图呢？建m条双向边，边权为正数，建k条单向边，边权为负数(时光逆流)。显然，我们只需判断整个图中是否存在一个权值之和为负数的回路即可。因为若存在了负环，沿着回路走，时间就会不断地减少，那么FJ就肯定能遇到当初那个时刻出发的自己。

spfa核心思想：构建一个队列，将松弛成功且不在队列的点加入队列中，同时将顶点v的入队次数加1并标记为true，表示该顶点在当前队列中，避免后面的顶点重复入队造成更新时间上的浪费，然后每出队一个点就将其标记为false，因为出队的顶点可能会对前面已更新的点到源点的距离有影响并可能再次入队，这样直到队列为空。如果队列中的某个顶点入队次数超过n次，就说明存在一个负环。为什么是大于n呢？如果是大于n-1，那么任意的单节点的图会被判定为存在负环，综合考虑取>n。

AC代码(141ms)：

 #include<iostream>

 #include<cstdio>

 #include<queue>

 #include<string.h>

 using namespace std;

 const int maxn=;

 int T,x,y,z,n,m,k,u,v,w,cnt[maxn],dis[maxn];vector<int> v1[maxn],v2[maxn];bool vis[maxn];queue<int> que;

 bool spfa(int s){

     while(!que.empty())que.pop();

     memset(vis,false,sizeof(vis));

     que.push(s),vis[s]=true,cnt[s]++,dis[s]=;//注意：自己到本身的时间为dis[s]=0，同时累计每个顶点的入队次数，用于判负环

     while(!que.empty()){

         u=que.front(),que.pop(),vis[u]=false;

         for(size_t j=;j<v1[u].size();++j){

             v=v1[u][j],w=v2[u][j];

             if(dis[u]+w<dis[v]){//松弛

                 dis[v]=dis[u]+w;

                 if(!vis[v]){

                     que.push(v),vis[v]=true;

                     if(++cnt[v]>n)return true;//如果第n+1次仍然更新，则存在负圈

                 }

             }

         }

     }

     return false;

 }

 int main(){

     while(~scanf("%d",&T)){

         while(T--){

             scanf("%d%d%d",&n,&m,&k);memset(cnt,,sizeof(cnt));

             for(int i=;i<=n;++i)v1[i].clear(),v2[i].clear();

             for(int i=;i<=n;++i)dis[i]=2e9;

             while(m--){

                 scanf("%d%d%d",&x,&y,&z);//建双向边

                 v1[x].push_back(y),v1[y].push_back(x);

                 v2[x].push_back(z),v2[y].push_back(z);

             }

             while(k--){

                 scanf("%d%d%d",&x,&y,&z);//建单向边，权值为负数，表示时间倒流

                 v1[x].push_back(y);

                 v2[x].push_back(-z);

             }

             if(spfa())puts("YES");

             else puts("NO");

         }

     }

     return ;

 }

秒客网