UVA558 - Wormholes(BellmanFord判负环卡塔 尔(英语:

作者: 计算机网络技术  发布:2019-11-15

UVA558 - Wormholes(BellmanFord判负环)

UVA558 - Wormholes(BellmanFord判负环)

UVA558 - Wormholes

主题材料轮廓:
有八个授课希望利用虫洞回到过去(照旧从那么些虫洞出来就到达了过去卡塔尔,给你虫洞造成的有向图,问教师能还是不可能回到过去。

解题思路:
选用BellmanFord判负环,如若不设有负环的话,那么最多通过N - 1次迭代就能够赢得最短路,因为形成最短路最多N - 1个节点(源点不算卡塔尔,但是借使存在了负环,那么就足以一贯迭代,最短路会愈加小。能够使用那么些本性来剖断是还是不是留存负环。

代码:

#include 
#include 
#include 

const int maxn = 1005;
const int maxm = 2005;

using namespace std;

struct edge {
    int u, v;
    int d;
}e[maxm];

const int INF = 0x7f7f7f7f;
int N, M;
int d[maxn];

bool BellmanFord() {
    for (int i = 0; i < N; i++)
        d[i] = i == 0 ? 0 : INF;

    d[0] = 0;
    for (int k = 0; k < N - 1; k++) 
        for (int i = 0; i < M; i++) {
            if (d[e[i].u] != INF && d[e[i].v] > d[e[i].u] + e[i].d)
                d[e[i].v] = d[e[i].u] + e[i].d;
        }

    for (int i = 0; i < M; i++)
        if (d[e[i].u] != INF && d[e[i].v] > d[e[i].u] + e[i].d) 
            return true;
    return false;
}

int main () {

    int T;
    scanf ("%d", &T);
    while (T--) {
        scanf ("%d%d", &N, &M);
        for (int i = 0; i < M; i++)
            scanf ("%d%d%d", &e[i].u, &e[i].v, &e[i].d);
        if (BellmanFord()) 
            printf ("possiblen");
        else
            printf ("not possiblen");
    }
    return 0;
}

- Wormholes(BellmanFord判负环卡塔 尔(英语:State of Qatar) UVA558 - Wormholes(BellmanFord判负环卡塔 尔(阿拉伯语:قطر‎ UVA558 - Wormholes 标题轮廓: 有三个执教希望利用虫洞回到过去(照旧从那...

Wormholes

Time Limit: 2000MS   Memory Limit: 65536K
Total Submissions: 46123   Accepted: 17033

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..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 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 (SET) 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.

Source

USACO 2006 December Gold

主题素材大体:
FJ有n块农场,编号为1到n,那n块农场由m条道路和w个虫洞连接,没条道路是双向的,权值为t1,表示经过每条道路需求费用t1个时刻单位,各个虫洞是单向的,权值为t2,经过每一个虫洞能够让您回到t2个时间单位以前(说白了就是时光倒流卡塔 尔(阿拉伯语:قطر‎;今后问您,FJ想从1号农场始发,经过若干农场后,在其启程早前的某不经常时回到1号农场。以后问你能无法完成。
分析:
我们把虫洞上的权值看成负的,那样难点就改成了问你那块农场中是还是不是留存负环的难题了。

 

单独spfa跑最短路,判二个点入队超越n次,就有负环,极慢。

那边写风度翩翩种极快的,dfs版的spfa。详见代码。

AC代码:

#include<cstdio>
#include<cstring>
#include<algorithm>
#define R register
using namespace std;
inline int read(){
    R int x=0;bool f=1;
    R char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=0;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return f?x:-x;
}
const int N=1e5+10;
int T,n,m1,m2;
struct node{
    int v,w,next;
}e[N<<1];
int tot,head[N],dis[N];
bool can,flag[N];
void add(int x,int y,int z){
    e[++tot].v=y;e[tot].w=z;e[tot].next=head[x];head[x]=tot;
}
void spfa(int x){
    flag[x]=1;
    for(int i=head[x];i;i=e[i].next){
        int v=e[i].v,w=e[i].w;
        if(dis[v]>dis[x]+w){
            if(flag[v]||can){can=1;break;}
            dis[v]=dis[x]+w;
            spfa(v);
        }
    }
    flag[x]=0;
}
void Cl(){
    can=0;tot=0;
    memset(dis,0,sizeof dis);//注意不是inf 
    memset(head,0,sizeof head);
    memset(flag,0,sizeof flag);
}
int main(){
    T=read();
    while(T--){
        Cl();
        n=read();m1=read();m2=read();
        for(int i=1,x,y,z;i<=m1;i++){
            x=read();y=read();z=read();
            add(x,y,z);
            add(y,x,z);
        }
        for(int i=1,x,y,z;i<=m2;i++){
            x=read();y=read();z=read();
            add(x,y,-z);
        }
        for(int i=1;i<=n;i++){
            spfa(i);
            if(can) break;
        }
        puts(can?"YES":"NO");
    }
    return 0;
}

 

 

 

 

本文由今晚买四不像发布于计算机网络技术,转载请注明出处:UVA558 - Wormholes(BellmanFord判负环卡塔 尔(英语:

关键词: