POJ 3259 Wormholes【bellman_ford判断负环——基础入门题】

时间:2021-05-17 20:01:29

链接:

http://poj.org/problem?id=3259

http://acm.hust.edu.cn/vjudge/contest/view.action?cid=22010#problem/B

Wormholes
Time Limit: 2000MS   Memory Limit: 65536K
Total Submissions: 25079   Accepted: 8946

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..NM (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, FF farm descriptions follow. 
Line 1 of each farm: Three space-separated integers respectively: NM, and W 
Lines 2..M+1 of each farm: Three space-separated numbers (SET) 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 (SET) 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
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.

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");
}
}