本文主要是介绍POJ - 3259 Wormholes（判断负环， Bellman Ford，SPFA），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
虫洞能够时光倒流，判断能否在回到出发的位置的时候在出发的时候之前。（判断是否存在负环）
初学最短路，尝试着用了三种方法判断：
1、Bellman Ford （令d全部为0，仅用来判断负环） OJ测试得157MS
2、Bellman Ford 结束后再来一轮松弛若松弛成功则存在负环。 235MS
3、Bellman Ford 用队列优化过的SPFA，判断是否存在一个点同队大于等于N次，若存在则表示存在负环。（WA！原因还没弄清楚，先留着，好像效率不太好，一般不用这种方式判断负环）
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int F, N, M, W;
const int MAXN = 501, MAXM = 5201, INF = 0x3f3f3f3f;
struct Edge
{int u, v, w;
}e[MAXM];
int d[MAXN];
int Bellman_Ford()
{memset(d, 0x3f, sizeof(d));d[1] = 0;for(int k = 0; k < N-1; k++)for(int i = 0; i < 2*M+W; i++){int u = e[i].u, v = e[i].v, w = e[i].w;if(d[u] < INF)d[v] = min(d[v], d[u] + w);}//判断负环 for(int i = 0; i < 2*M+W; i++){int u = e[i].u, v = e[i].v, w = e[i].w;if(d[v] > d[u] + w)return 1;}return 0;
}
//d=0判断负环
bool find_negative_loop()
{memset(d, 0, sizeof(d));for(int i = 0; i < N; i++)for(int j = 0; j < 2*M+W; j++){int u = e[j].u, v = e[j].v, w = e[j].w;if(d[v] > d[u] + w){d[v] = d[u] + w;if(i == N-1) return true;}}return false;
}#include <queue>
int first[MAXN], nexte[MAXM], times[MAXN];
bool inq[MAXN];
int SPFA()
{queue<int> q;memset(times, 0, sizeof(times));memset(d, 0x3f, sizeof(d));d[1] = 0;memset(inq, 0, sizeof(inq));q.push(0);while(q.size()){int u = q.front(); q.pop();inq[u] = false; //清除标志for(int i = first[u]; i != -1; i = nexte[i]) //M条边{int u = e[i].u, v = e[i].v, w = e[i].w;if(d[v] > d[u] + w){d[v] = d[u] + w;if(!inq[v]){times[v]++;if(times[v] >= N)return 1;inq[v] = true;q.push(v);}}}}return 0;
}int main()
{//freopen("in.txt", "r", stdin);scanf("%d", &F);while(F--){scanf("%d%d%d", &N, &M, &W);for(int i = 1; i <= N; i++) first[i] = -1;for(int i = 0; i < 2*M; i+=2){scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w);e[i+1].u = e[i].v, e[i+1].v = e[i].u, e[i+1].w = e[i].w;nexte[i] = first[e[i].u];first[e[i].u] = i;nexte[i+1] = first[e[i+1].u];first[e[i+1].u] = i;}for(int i = 2*M; i < 2*M+W; i++){scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w);e[i].w *= -1;nexte[i] = first[e[i].u];first[e[i].u] = i;}printf(find_negative_loop() ? "YES\n" : "NO\n");//printf(Bellman_Ford() ? "YES\n" : "NO\n");//printf(SPFA() ? "YES\n" : "NO\n");}return 0;
}这篇关于POJ - 3259 Wormholes（判断负环， Bellman Ford，SPFA）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
