链接：
http://poj.org/problem?id=3259http://acm.hust.edu.cn/vjudge/contest/view.action?cid=22010#problem/B
Wormholes
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 comprisesN (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 Ethat 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 Ethat 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 Sample Output NO 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. Source USACO 2006 December Gold |
题意：
农夫 FJ 有 N 块田地【编号 1...n】 (1<=N<=500)
田地间有 M 条路径 【双向】(1<= M <= 2500)
同时有 W 个孔洞,可以回到以前的一个时间点【单向】(1<= W <=200)
问：FJ 是否能在田地中遇到以前的自己
算法：bellman_ford 判断是否有负环
思路：
田地间的双向路径加边,权值为正
孔洞间的单向路径加边,权值为负【可以回到以前】
判断有向图是否存在负环
因为如果存在了负数环,时间就会不停的减少,
那么 FJ 就可以回到以前更远的地方,肯定能遇到以前的自己的
PS：第一次做这个的童鞋,如果实在无法理解，就按照上面的样例和思路画个图就好了，反正才三个点。 两年了，居然如此经典的入门题目都没有遇到过，真不知道我干什么去了Orz
code：
| 3259 | Accepted | 180K | 63MS | C++ | 1707B |
/********************************************************************
Accepted180 KB47 msC++2509 B
题意：农夫 FJ 有 N 块田地【编号 1...n】 (1<=N<=500)
田地间有 M 条路径 【双向】(1<= M <= 2500)
同时有 W 个孔洞,可以回到以前的一个时间点【单向】(1<= W <=200)
问：FJ 是否能在田地中遇到以前的自己
算法：bellman_ford 判断是否有负环
思路：田地间的双向路径加边,权值为正
孔洞间的单向路径加边,权值为负【可以回到以前】
判断有向图是否存在负环
因为如果存在了负数环,时间就会不停的减少,
那么 FJ 就可以回到以前更远的地方,肯定能遇到以前的自己的
*******************************************************************/
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
using namespace std;
const int maxn = 510;
const int maxw = 2500*2+200+10;
const int INF = 10000;
int d[maxn];
int n,m;
struct Edge{
int u,v;
int t;
}edge[maxw];
bool bellman_ford()
{
for(int i = 1; i <= n; i++) d[i] = INF; //初始化从起点到 i 时间为最值
d[1] = 0; //起点为 0
for(int i = 1; i < n; i++)
{
bool flag = true; //判断这轮是否能够松弛
for(int j = 0; j < m; j++)
{
int u = edge[j].u;
int v = edge[j].v;
int t = edge[j].t;
if(d[v] > d[u]+t) //松弛操作
{
d[v] = d[u]+t;
flag = false;
}
}
if(flag) return false; //如果当前轮不能松弛,直接判断没有负数环
}
for(int i = 0; i < m; i++)
{
if(d[edge[i].v] > d[edge[i].u]+edge[i].t)
return true;//如果仍然能够松弛则存在负环
}
return false;
}
int main()
{
int T;
int M,W;
scanf("%d", &T);
while(T--)
{
scanf("%d%d%d", &n,&M,&W);
m = 0;
int u,v,t;
for(int i = 1; i <= M; i++) //田地间的大路,加双边
{
scanf("%d%d%d", &u,&v,&t);
edge[m].u = u;
edge[m].v = v;
edge[m++].t = t;
edge[m].u = v;
edge[m].v = u;
edge[m++].t = t;
}
for(int i = 1; i <= W; i++) //孔洞,加单边
{
scanf("%d%d%d", &u,&v,&t);
edge[m].u = u;
edge[m].v = v;
edge[m++].t = -t;
}
if(bellman_ford()) printf("YES\n"); //存在负数环
else printf("NO\n");
}
}