POJ3259Wormholes（判断是否存在负回路）

Wormholes

Time Limit: 2000MS		Memory Limit: 65536K
Total Submissions: 38300		Accepted: 14095

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，W;N表示点的个数，M表示正权的边数，无向的，W表示负权边数，有向，

如果存在负回路则输出yes否则no

自己真是够脑残，两个代码找错找了半天，尽然都是一些手残的原因

1：SPFA

若一个点最短路被改进的次数达到n ，则有负权环。可以用spfa算法判断图有无负权环

  1 #include <iostream>
  2 #include <cstring>
  3 #include <algorithm>
  4 #include <cstdio>
  5 #include <vector>
  6 #include <queue>
  7 using namespace std;
  8 const int INF = 100000000;
  9 const int MAX = 1000 + 10;
 10 struct point
 11 {
 12     int e,w;
 13 };
 14 int F,M,N,W;
 15 vector<point> g[MAX];
 16 int updatetimes[MAX],dist[MAX];
 17 /*
 18 int spfa(int v)
 19 {
 20     for( int i = 1; i <= N; ++i)
 21         dist[i] = INF;
 22     dist[v] = 0;
 23     queue<int> que;
 24     que.push(v);
 25     memset(updatetimes ,0,sizeof(updatetimes));
 26     while( !que.empty()) {
 27         int s = que.front();
 28         que.pop();
 29         for( int i = 0;i < g[s].size(); ++i) {
 30             int e = g[s][i].e;
 31             if( dist[e] > dist[s] + g[s][i].w ) {
 32                 dist[e] = dist[s] + g[s][i].w;
 33                 que.push(e);
 34                  ++updatetimes[e];
 35                  if( updatetimes[e] >= N)
 36                      return true;
 37             }
 38         }
 39     }
 40     return false;
 41 }
 42 */
 43 int spfa(int v)
 44 {
 45     for(int i = 1; i <= N; i++)
 46         dist[i] = INF;
 47     dist[v] = 0;
 48     queue<int> que;
 49     que.push(v);
 50     memset(updatetimes,0,sizeof(updatetimes));
 51     while(que.size())
 52     {
 53         int s = que.front();
 54         que.pop();
 55         int len = g[s].size();
 56         for(int i = 0; i < g[s].size(); i++)
 57         {
 58             int e = g[s][i].e;
 59             if(dist[e] > dist[s] + g[s][i].w)
 60             {
 61                 dist[e] = dist[s] + g[s][i].w;
 62                 que.push(e);
 63                 ++updatetimes[e];
 64                 if(updatetimes[e] >= N)
 65                     return true;
 66             }
 67         }
 68     }
 69     return false;
 70 }
 71 
 72 int main()
 73 {
 74     scanf("%d", &F);
 75     while(F--)
 76     {
 77          scanf("%d%d%d", &N,&M,&W);
 78          for(int i = 0; i < MAX; i++)
 79                 g[i].clear();
 80          point edge;
 81          for(int i = 0; i < M; i++)
 82          {
 83              int s,e,w;
 84              scanf("%d%d%d", &s,&e,&w);
 85              edge.e = e;
 86              edge.w = w;
 87              g[s].push_back(edge);
 88              edge.e = s;
 89              g[e].push_back(edge);
 90          }
 91          for(int i = 0; i < W; i++)
 92          {
 93              int s,e,w;
 94              scanf("%d%d%d", &s,&e,&w);
 95              edge.e = e;
 96              edge.w = (-1) * w;
 97              g[s].push_back(edge);
 98          }
 99          if(spfa(1))
100          {
101              printf("YES
");
102          }
103          else
104          {
105              printf("NO
");
106          }
107     }
108     return 0;
109 }

View Code

2.Ballem-ford

Bellman-Ford:算法核心就是对每个点更新一下dist[](离原点的距离)，怎么更新一个点呢，通过枚举每个边就可以了，所以每次把所有的边枚举一遍，专业术语叫做<松弛操作>就可以确定一个点的dist，除了原点一共需要N-1个点，所以套个循环

至于判断是否存在负环呢，就在更新完所有dist,然后在枚举一下每个边，看看是否通过在增加一个边能让dist再减少，如果可以的话那就是存在负回路，因为在前面我们已经更新到最短的路径了。

 1 #include <iostream>
 2 #include <cstring>
 3 #include <algorithm>
 4 #include <cstdio>
 5 #include <vector>
 6 using namespace std;
 7 const int INF = 10000000;
 8 struct Edge
 9 {
10     int s,e,w;
11 };
12 vector<Edge> edge;
13 int dist[1000 + 10];
14 int N,W,M;
15 
16 bool Ballem_ford(int v)
17 {
18     for(int i = 1; i <= N; i++)
19     {
20         dist[i] = INF;
21     }
22     dist[v] = 0;
23     int len = edge.size();
24     for(int i = 1; i < N; i++)
25     {
26         for(int j = 0; j < len; j++)
27         {
28             int s = edge[j].s;
29             int e = edge[j].e;
30             if(dist[e] > dist[s] + edge[j].w)   //把j写成了i,真是无语 
31                 dist[e] = dist[s] + edge[j].w;
32         }
33     }
34     for(int i = 0; i < len; i++)
35     {
36         int s = edge[i].s;
37         int e = edge[i].e;
38         if(dist[e] > dist[s] + edge[i].w)
39             return true;
40     }
41     return false;
42 }
43 int main()
44 {
45     int F;
46     scanf("%d", &F);
47     while(F--)
48     {
49         scanf("%d%d%d",&N,&M,&W);
50         edge.clear();
51         Edge point,temp;
52         for(int i = 0; i < M; i++)
53         {
54             scanf("%d%d%d",&point.s,&point.e,&point.w);
55             edge.push_back(point);
56             temp.s = point.e;
57             temp.e = point.s;
58             temp.w = point.w;
59             edge.push_back(temp);
60         }
61         for(int i = 0; i < W; i++)
62         {
63             scanf("%d%d%d", &point.s,&point.e,&point.w);
64             point.w = (-1) * point.w;
65             edge.push_back(point);
66         }
67         if(Ballem_ford(1) == true)
68             printf("YES
");
69         else
70             printf("NO
");
71     }
72     return 0;
73 }

View Code