Coder Space

题意：
农场上有N块田地（N < = 500），M条路径（M <= 2500）可以从i到达j花费t单位时间。另外还有W个虫洞（W <= 200），虫洞可以从一块地 i 到达另一块地j并且时间倒退t。注意路径是双向的，虫洞是单向的。现在农夫John希望知道能否从某块地出发并且回到这块地，使得他回来的时间早于出发的时间。

思路：
根据题意，题目其实是要求一个带负权的有向图中是否存在权值为负的回路。经典的Bellman_Ford算法正是算法过程中就要判断这一问题。由于John出发点不确定，一个原始的想法是，枚举起点，复杂度为O(n^4)。另一更好的解法是，假设有一超级源点，到各点的距离为0，那么只需从这个源点出发，判断图中可能出现的负环，即只需设初值d[i] = 0，执行一次Bellman_Ford算法即可。

源代码
  1#include<iostream>
  2#include<limits>
  3
  4using namespace std;
  5
  6const int MAXN = 501;
  7const int MAXE = 5201;
  8const int INF = numeric_limits<int>::max();
  9
 10struct Edge
 11{
 12    int s;
 13    int e;
 14    int w;
 15};
 16
 17int G[MAXN][MAXN];
 18Edge edges[MAXE];
 19
 20bool BellmanFord(int n, int k)               //Bellman_Ford算法判断是否存在负权回路
 21{
 22    int d[MAXN];
 23    bool flag;
 24    
 25    for(int i=1; i<=n; i++)                  //增加到各点距离为0的超级源点
 26    {
 27        d[i] = 0;
 28    }
 29
 30    for(int j=1; j<n; j++)
 31    {
 32        flag = false;
 33        for(int i=1; i<=k; i++)
 34        {
 35            if(d[edges[i].e] > d[edges[i].s] + edges[i].w)     //松弛操作
 36            {
 37                d[edges[i].e] = d[edges[i].s] + edges[i].w;
 38                flag = true;
 39            }
 40        }
 41        if(!flag)
 42        {
 43            return true;
 44        }
 45    }
 46
 47    for(int i=1; i<=k; i++)
 48    {
 49        if(d[edges[i].e] > d[edges[i].s] + edges[i].w)
 50        {
 51            return false;
 52        }
 53    }
 54    return true;
 55}    
 56
 57int main()
 58{
 59    int F;
 60    int N,M,W;
 61    int s,e,t;
 62    int cntE;
 63
 64    int i,j;
 65
 66    cin>>F;
 67    while(F--)
 68    {
 69        cin>>N>>M>>W;
 70
 71        for(i=1; i<=N; i++)
 72        {
 73            for(j=1; j<=N; j++)
 74            {
 75                G[i][j] = INF;
 76            }
 77        }
 78
 79        for(i=0; i<M; i++)
 80        {
 81            cin>>s>>e>>t;
 82            if(G[s][e] > t)               //因有重边，不能直接存储边
 83            {
 84                G[s][e] = t;
 85                G[e][s] = t;
 86            }
 87        }
 88        for(i=0; i<W; i++)
 89        {
 90            cin>>s>>e>>t;
 91            G[s][e] = -1 * t;
 92        }
 93
 94        cntE = 0;
 95        for(i=1; i<=N; i++)             //从邻接矩阵中提取边，如果边较少，可有效降低Bellman_Ford的复杂度
 96        {
 97            for(j=1; j<=N; j++)
 98            {
 99                if(G[i][j] != INF)
100                {
101                    ++cntE;
102                    edges[cntE].s = i;
103                    edges[cntE].e = j;
104                    edges[cntE].w = G[i][j];
105                }
106            }
107        }
108
109        if(BellmanFord(N,cntE))
110        {
111            cout<<"NO"<<endl;
112        }
113        else
114        {
115            cout<<"YES"<<endl;
116        }
117    }
118    //system("Pause");
119    return 0;
120}