Wormholes POJ 3259（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.

题目意思:对于t组输入输出，有N个点，M条双向通路，K个虫洞。虫洞是一个单向的通路。问能否从某一个点出发，通过一些路径和虫洞，返回到出发点，并且时间还要早于出发时间，这样他就能够遇到他自己了。

解题思路：又是John，想都不用想又是USACO的题，美国果然是农业立国啊。在第二组样例中，John沿着1->2->3->1，从第一个点出发回到第一个点，所需时间为-1，这样他就能够遇到自己了。这该怎么思考？遇到虫洞会回到过去，时间回溯。实际上就是要求判断一个带有负权的有向网中是否存在负权值回路，

我们知道可以使用Bellman-Ford可以判断是否存在负环，因为出现了负值回路后会不断的松弛。这里我们用优化后的SPFA来实现。

原理：如果存在负权值回路，那么从源点到某一个点的最短路径可以无限缩短，某些顶点入队列将会超过N次（N为顶点个数）。

ps:代码有给出了另外一种判断是否有负环的方法，时间会更快。从任意一点出发求最短路，必定会求出到其他所有点的最短路，若其中某个点在一个负权回路中，那么它肯定会不断地走这个回路以使到这个点的花费越小越好，这时候该点到出发点的距离就会为负值，所以只需从一个点开始便能找到是否存在负回路，这里我们就只看从源点到源点的dis就可以了。

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<queue>
  4 #include<algorithm>
  5 #define INF 0x3f3f3f3f
  6 #define maxs 10010
  7 using namespace std;
  8 struct node
  9 {
 10     int to;
 11     int w;
 12 } t;
 13 vector<node>Map[maxs];
 14 int dis[maxs];
 15 int vis[maxs];
 16 int n,m,k;
 17 void add(int s,int e,int w)
 18 {
 19     t.to=e;
 20     t.w=w;
 21     Map[s].push_back(t);
 22 }
 23 void init()
 24 {
 25     int i;
 26     memset(dis,INF,sizeof(dis));
 27     memset(vis,0,sizeof(vis));
 28     for(i=0; i<=n; i++)
 29     {
 30         Map[i].clear();
 31     }
 32 }
 33 int SPFA(int s)
 34 {
 35     int cnt[maxs]= {0};///记录每个点入队次数
 36     int i;
 37     dis[s]=0;
 38     vis[s]=1;
 39     queue<int>q;
 40     q.push(s);
 41     cnt[s]++;
 42     while(!q.empty())
 43     {
 44         int u=q.front();
 45         /*if(cnt[u]>=n)
 46         {
 47             return 0;///这里用来判断入队列是否超过N次
 48         }*/
 49         q.pop();
 50         vis[u]=0;
 51         for(i=0; i<Map[u].size(); i++)
 52         {
 53             int to=Map[u][i].to;
 54             if(dis[to]>dis[u]+Map[u][i].w)
 55             {
 56                 dis[to]=dis[u]+Map[u][i].w;///松弛操作
 57                 if(dis[1]<0)///这种判断是否有负环的更快。如果起始点的dis[s]<0说明存在负环
 58                 {
 59                     return 0;
 60                 }
 61                 if(!vis[to])
 62                 {
 63                     vis[to]=1;
 64                     q.push(to);
 65                     cnt[to]++;
 66                 }
 67             }
 68         }
 69     }
 70     return 1;
 71 }
 72 int main()
 73 {
 74     int t,i,j,u,v,w;
 75     scanf("%d",&t);
 76     for(i=1; i<=t; i++)
 77     {
 78         scanf("%d%d%d",&n,&m,&k);
 79         init();
 80         while(m--)
 81         {
 82             scanf("%d%d%d",&u,&v,&w);
 83             add(u,v,w);
 84             add(v,u,w);
 85         }
 86         while(k--)
 87         {
 88             scanf("%d%d%d",&u,&v,&w);
 89             add(u,v,-w);///虫洞时间取负值
 90         }
 91         if(SPFA(1))
 92         {
 93             printf("NO
");
 94         }
 95         else
 96         {
 97             printf("YES
");
 98         }
 99     }
100     return 0;
101 }

这里再附上使用邻接矩阵和Bellman-Ford算法的代码。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define inf 0x3f3f3f3f
struct Edge
{
    int f;///起点
    int t;///终点
    int c;///距离
} edge[6000];
int dist[505];
int n,m,h,cnt;
int bellman_ford()
{
    memset(dist,inf,sizeof(dist));
    dist[1]=0;///起点
    int i,j;
    for(j=1; j<=n; j++)
    {
        for(i=1; i<=cnt; i++)
        {
            if(dist[edge[i].t]>dist[edge[i].f]+edge[i].c)///松弛操作
            {
                dist[edge[i].t]=dist[edge[i].f]+edge[i].c;
            }
        }
    }
    int flag=1;
    for(i=1; i<=cnt; i++)///遍历所有的边
    {
        if(dist[edge[i].t]>dist[edge[i].f]+edge[i].c)
        {
            flag=0;///存在从源点可达的负权回路
            break;
        }
    }
    return flag;
}
int main()
{
    int i,t;
    scanf("%d",&t);
    while(t--)
    {
        cnt=0;
        scanf("%d %d %d",&n,&m,&h);
        int u,v,w;
        for(i=1; i<=m; i++)
        {
            cnt++;
            scanf("%d %d %d",&u,&v,&w);
            edge[cnt].f=u;
            edge[cnt].t=v;
            edge[cnt].c=w;
            cnt++;
            edge[cnt].f=v;
            edge[cnt].t=u;
            edge[cnt].c=w;
        }
        for(i=1; i<=h; i++)
        {
            cnt++;
            scanf("%d %d %d",&u,&v,&w);
            edge[cnt].f=u;
            edge[cnt].t=v;
            edge[cnt].c=-w;
        }
        if(bellman_ford())
            printf("NO
");
        else
            printf("YES
");
    }
    return 0;
}