【代码超详解】POJ 3259 虫洞（Bellman-Ford算法 · 板子题）

程序员文章站 2024-03-23 13:29:22

...

一、题目描述

Wormholes

Time Limit: 2000MS Memory Limit: 65536K
Total Submissions: 76233 Accepted: 28356（2019/10/22）

Description

当走访自己的农场时，农夫 John（下称 FJ）发现了许多神奇的虫洞。虫洞是一个很奇怪的东西，因为它是一个能够将你送到一个时间位于你进入虫洞之前的目的地的单向路径。FJ 的每个农场包含 N 块田（1 ≤ N ≤ 500），编号从 1 到 N ，M 条路（1 ≤ M ≤ 2500），W 个虫洞（1 ≤ W ≤ 200）。
FJ 是一个*的时间旅行爱好者，他希望做这样的事：从某块田开始，经过一些路径和虫洞，最后回到起始位置且到达时的时间在他出发之前。他有可能与他自己碰面 ???? 。
为了帮助 FJ 求出这是否可能成功，他会告诉你他的农场的 F 个地图（1 ≤ F ≤ 5）。没有路径花费超过 10 000 秒才能走完，也没有虫洞能够将 FJ 带回早于进入虫洞的时刻的 10 000 秒之前。

Input

第一行：一个整数 F ，描述如上。
接下来对每个农场，第一行三个整数，空格分隔：N、M、W。
接下来 M 行，每行三个整数，空格分隔：S、E、T，分别描述：存在点 S 到点 E 的双向路径，单程花费 T 秒。两块田之前可以被超过一条路连接。
接下来 W 行，每行三个整数，空格分隔：S、E、T，分别描述：存在点 S 到点 E 的单向路径，能够令进入者回到 T 秒之前。

Output

1 到 F 行：对每个农场，如果 FJ 可以达成他的目标，输出

YES

否则输出

NO

Sample Input

Sample Output

NO
YES

Hint

对农场 1，FJ 并不能穿越到出发之前。
对农场 2，FJ 可以沿闭环 1→2→3→1 行进，在他出发之前回到出发地 1。他可以从这个环路上的任意位置出发来完成目标。

Source

USACO 2006 December Gold

二、算法分析说明

Bellman-Ford算法

1、用途：求图的定点到其余点的最短距离。
2、条件限制：要求不存在负环（权和为负的回路）。
3、算法内容：
设图G(V, E)，定点s，数组d[|V|]代表定点s到各点的距离。
对任意的边uv，如果|sv|>|su|+|uv|即d[v]>d[u]+weight(u, v)，则令|sv|=|su|+|uv|即d[v]=d[u]+weight(u, v)。
不断缩小估计最短距离，直到某次遍历全部边后发现未进行更新操作。
证明：待填坑。
4、算法性质：
【1】当存在负环时，会给出错误的结果。
【2】当不存在负环时，遍历次数不超过|V|－1。所以，算法的时间复杂度为O(|V||E|)。
证明：待填坑。
5、检测是否存在负环的算法：
在进行本算法的同时统计更新次数（遍历次数），达到|V|时，判定存在负环。
或者，强制更新|V|－1次，如果仍然存在|sv|>|su|+|uv|即d[v]>d[u]+weight(u, v)的边uv，则该图存在负环。
6、坑点小结：
【1】由于可能要求输入负权边，因此相关的数据类型**不能采用无符号类型**。
【2】为了能够顺利比较距离，应该先令除了指定的源点（定点）之外的点的距离全部设为一个较大的值（任意选定的定点到自己的距离为零）。
这个值应该根据题目给出的数据范围而定，但**不要过大**，否则会导致溢出，从而WA。

对于本题，用该算法判定是否存在负环，即得到结果。需要注意的是，两个农田之前的一般路径是双向的，每读入一条边，需要存入两条起点和终点相同但方向相反的边。而连通两块田的虫洞则是单向的。
通行时间为每条边的权值，但虫洞会将进入者送回之前的时间，所以读入描述虫洞的单向边以后要将权值改成负值，否则不能通过样例。
本题为Bellman-Ford算法的模板题，算法内容已经说得很清楚，将不会撰写代码编写指导和注释。

三、AC 代码（110 ms）

#include<cstdio>
#include<algorithm>
#pragma warning(disable:4996)
using namespace std;
struct edge { int u, v, t; };
int F, M, N, W, d[501], p, t; edge e[5201];
inline bool HasNegLoop() {
	int T = 1;
	for (;;) {
		for (int i = 1; i <= t; ++i) {
			if (d[e[i].v] > d[e[i].u] + e[i].t)d[e[i].v] = d[e[i].u] + e[i].t;
		}
		++T; if (T == N)break;
	}
	for (int i = 1; i <= t; ++i)if (d[e[i].v] > d[e[i].u] + e[i].t)return true;
	return false;
}
int main() {
	scanf("%d", &F); ++F;
	while (--F) {
		scanf("%d%d%d", &N, &M, &W); fill(d + 2, d + N + 1, 200000000); d[1] = 0;
		t = 2 * M;
		for (p = 1; p <= t; ++p) {
			scanf("%d%d%d", &e[p].u, &e[p].v, &e[p].t);
			++p; e[p].u = e[p - 1].v, e[p].v = e[p - 1].u, e[p].t = e[p - 1].t;
		}
		t += W;
		for (; p <= t; ++p) {
			scanf("%d%d%d", &e[p].u, &e[p].v, &e[p].t); e[p].t = -e[p].t;
		}
		switch (HasNegLoop()) {
		case false:puts("NO"); continue;
		default:puts("YES");
		}
	}
	return 0;
}