POJ 3259 Wormholes Bellman-Ford算法模板题 SPAF模板题

题目链接

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

2
3 3 1
1 2 2
1 3 4
2 3 1
3 1 3
3 2 1
1 2 3
2 3 4
3 1 8
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.

题目大意：
现有 N 块田地【编号 1…n】 (1<=N<=500)
田地间有 M 条路径 【双向】(1<= M <= 2500)
同时有 W 个虫洞，可以借助虫洞回到以前的一个时间点【单向】(1<= W <=200)
问能否通过虫洞回到过去。

解题思路：
本题的本质就是判断该图是否存在负权回路，可使用 Bellman-Ford算法进行判断。 Bellman-Ford算法与迪杰斯特拉算法一样都是求单源最短路的算法。

Bellman-Ford算法模板

bool bellman_ford() {
    init();/*如果在图中不存在从s可达的负圈，那么最短路不会经过同一个顶点两次，也就是说，最多通过|V|-1条边*/for (int i = 1; i < n; i++) {
    //循环次数 结点数减1bool change = false;//用于判断本次循环是否发生了松弛操作for (int j = 1; j <= cnt; j++) {
    //遍历所有的边if (d[list[j].to] > d[list[j].from] + list[j].cost) {
    d[list[j].to] = d[list[j].from] + list[j].cost;change = true;}}if (!change) break;//如果没有发现更短的路径，则可以提前剪枝 其实这里可以直接return false 即不存在负权环}for (int j = 1; j <= cnt; j++) {
    if (d[list[j].to] > d[list[j].from] + list[j].cost) {
    return true;//如果结点数减1次循环结束之后还可以进行松弛操作，则存在负权环}}return false;
}

AC代码：

#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
const int maxn = 510;
int d[maxn];
#define INF 0x3fffffff
struct e {
    int from, to, cost;
}list[6000];
int n, m, w, cnt;
void init() {
    for (int i = 1; i <= n; i++) {
    d[i] = INF;}d[1] = 0;//这里我们把1号结点当作了出发点，整个算法结束之后，如果不存在负权环，则同时也求出了从结点1到其余各个结点的最短路径
}
bool bellman_ford() {
    init();/*如果在图中不存在从s可达的负圈，那么最短路不会经过同一个顶点两次，也就是说，最多通过|V|-1条边*/for (int i = 1; i < n; i++) {
    //循环次数 结点数减1bool change = false;//用于判断本次循环是否发生了松弛操作for (int j = 1; j <= cnt; j++) {
    //遍历所有的边if (d[list[j].to] > d[list[j].from] + list[j].cost) {
    d[list[j].to] = d[list[j].from] + list[j].cost;change = true;}}if (!change) break;//如果没有发现更短的路径，则可以提前剪枝 其实这里可以直接return false 即不存在负权环}for (int j = 1; j <= cnt; j++) {
    if (d[list[j].to] > d[list[j].from] + list[j].cost) {
    return true;//如果结点数减1次循环结束之后还可以进行松弛操作，则存在负权环}}return false;
}
int main() {
    int T;scanf("%d", &T);while (T--) {
    scanf("%d%d%d", &n, &m, &w);int s, e, t; cnt = 0;for (int i = 1; i <= m; i++) {
    //在此处无需处理重边的情况scanf("%d%d%d", &s, &e, &t);list[++cnt].from = s;list[cnt].to = e;list[cnt].cost = t;list[++cnt].from = e;list[cnt].to = s;list[cnt].cost = t;}for (int i = 1; i <= w; i++) {
    scanf("%d%d%d", &s, &e, &t);list[++cnt].from = s;list[cnt].to = e;list[cnt].cost = -t;}if (bellman_ford()) cout << "YES" << endl;else cout << "NO" << endl;}
}

关于 Bellman-Ford算法的原理，可参考这位大神的博客：
深入理解Bellman-Ford（SPFA）算法

SPFA是对 Bellman-Ford算法的优化，我们考虑一个节点入队的条件是什么，只有那些在前一遍松弛中改变了距离估计值的点，才可能引起他们的邻接点的距离估计值的改变。因此，用一个先进先出的队列来存放被成功松弛的顶点。同样，我们有这样的定理：“两点间如果有最短路，那么每个结点最多经过一次。也就是说，这条路不超过n-1条边。”（如果一个结点经过了两次，那么我们走了一个圈。如果这个圈的权为正，显然不划算；如果是负圈，那么最短路不存在；如果是零圈，去掉不影响最优值）。也就是说，每个点最多入队n-1次（这里比较难理解，需要仔细体会，n-1只是一种最坏情况，实际中，这样会很大程度上影响程序的效率）。

有了上面的基础，思路就很显然了，加开一个数组记录每个点入队的次数（num），然后，判断当前入队的点的入队次数，如果大于n-1，则说明存在负权回路。
关于 SPFA算法的原理，可参考这位大神的博客：
SPAF

SPAF模板：

bool spaf(int s, int num) {
    init(s);queue<int> que;while (!que.empty()) {
     que.pop(); }que.push(s);vis[s] = true; cnt[s]++;while (!que.empty()) {
    int u = que.front();que.pop();vis[u] = false;for (int i = 0; i < E[u].size(); i++) {
    int v = E[u][i].to;if (d[u] != INF && d[v] > d[u] + E[u][i].cost) {
    d[v] = d[u] + E[u][i].cost;if (!vis[v]) {
    que.push(v);vis[v] = true;if (++cnt[v] >= num) return true;}}}}return false;
}

AC代码：

#include<iostream>
#include<queue>
#include<vector>
#include<stdio.h>
#include<algorithm>
using namespace std;
const int maxn = 510;
#define INF 0x3fffffff
struct e {
    int to, cost;
};//边信息
vector<e> E[maxn];
int n, m, w;
void addedge(int u, int v, int w) {
    e now; now.to = v; now.cost = w;E[u].push_back(now);//意味着这条边从u出发
}
int d[maxn];//保存最小距离
bool vis[maxn];//在队列标志
int cnt[maxn];//每个结点入队列的次数
void init(int s) {
    //初始化for (int i = 1; i <= n; i++) {
    d[i] = INF; vis[i] = false; cnt[i] = 0;}d[s] = 0;
}
bool spaf(int s, int num) {
    init(s);queue<int> que;while (!que.empty()) {
     que.pop(); }que.push(s);vis[s] = true; cnt[s]++;while (!que.empty()) {
    int u = que.front();que.pop();vis[u] = false;for (int i = 0; i < E[u].size(); i++) {
    int v = E[u][i].to;if (d[u] != INF && d[v] > d[u] + E[u][i].cost) {
    d[v] = d[u] + E[u][i].cost;if (!vis[v]) {
    que.push(v);vis[v] = true;if (++cnt[v] >= num) return true;//判断是否存在负权环}}}}return false;
}
int main() {
    int T;scanf("%d", &T);while (T--) {
    scanf("%d%d%d", &n, &m, &w);for (int i = 1; i <= n; i++) {
    E[i].clear();//注意要清空之前的边信息！！！}int s, e, t;for (int i = 1; i <= m; i++) {
    //在此处无需处理重边的情况scanf("%d%d%d", &s, &e, &t);//双向addedge(s, e, t);addedge(e, s, t);}for (int i = 1; i <= w; i++) {
    //单向scanf("%d%d%d", &s, &e, &t);addedge(s, e, -t);}if (spaf(1, n)) cout << "YES" << endl;else cout << "NO" << endl;}
}