POJ 3259 Wormholes(判负环)

比眉伴天荒 2022-05-17 05:57 185阅读 0赞

[题目链接][Link 1]

题目大意：农夫John在它的许多农场探险时，他发现了许多奇异的虫洞，虫洞的特别在于虫洞是单向路径，可以让你在进入虫洞之前到达目的地，John的农场从1-N进行编号，有M条农场与农场之间的双向路径和W个虫洞。因为农夫John是一个时间旅行的狂热爱好者，他想做以下的一些事情：从某块农田开始，经过一些路径和虫洞，他想回到最开始出发的那个地点的时间之前，这样也许他就能遇见自己。如果能就输出“YES”，否则输出“NO”。

输入  
第1行：一个整数F表示接下来会有F个农场说明(也可以认为是F组测试数据)。

每个农场的第1行：有3个空格分开的整数N、M和W。（1 ≤ *N* ≤ 500，1 ≤ *M* ≤ 2500，1 ≤ *W* ≤ 200）

第2行到第M+1行：有3个空格分开的整数(S, E, T) 描述一条从S到E的双向路径，这条路径将耗时T秒。

第M+2行到M+W+1行：有3个空格分开的整数(S, E, T) 描述一条从S到E的单向路径，它会让John回到过去T秒。

分析：要经过一圈后回到初始点的时间在出发之前，其实也就是找到一个环的，它上面的边权相加是负，如果能找到，那么走一圈以后就会回到过去，如果找不到负环，就输出“NO”，那么就直接可以用Bellman-For来判负环。

#include<map>
    #include<set>
    #include<cmath>
    #include<queue>
    #include<stack>
    #include<cstdio>
    #include<vector>
    #include<cctype>
    #include<cstring>
    #include<utility>
    #include<cstdlib>
    #include<iomanip>
    #include<iostream>
    #include<algorithm>
    #define Clear(x) memset(x,0,sizeof(x))
    #define fup(i,a,b) for(int i=a;i<b;i++)
    #define rfup(i,a,b) for(int i=a;i<=b;i++)
    #define fdn(i,a,b) for(int i=a;i>b;i--)
    #define rfdn(i,a,b) for(int i=a;i>=b;i--)
    typedef long long ll;
    using namespace std;
    const double pi=acos(-1.0);
    const int maxn = 5e2+7;
    const int maxn1 = 2505;
    const int inf = 0x3f3f3f3f;
    int tot;
    int N,M,W;
    int dis[maxn];
     
    struct Node{
        int u,v,w;
    }edge[maxn1<<1];
     
    void addEdge(int u,int v,int w)
    {
        edge[tot].u=u;
        edge[tot].v=v;
        edge[tot++].w=w;
    }
     
     
    bool bellman_ford()
    {
        memset(dis,inf,sizeof(dis));
        dis[1]=0;
        bool flag;
        rfup(i,1,N-1)
        {
            flag=true;
            fup(j,0,tot)
            {
                if(dis[edge[j].v]>dis[edge[j].u]+edge[j].w)
                {
                    dis[edge[j].v]=dis[edge[j].u]+edge[j].w;
                    flag=false;
                }
            }
            if(flag) break;
        }
        fup(i,0,tot)
        {
            if(dis[edge[i].v]>dis[edge[i].u]+edge[i].w)
                return true;
        }
        return false;
    }
     
    int main()
    {
        int F,S,E,T;
        scanf("%d",&F);
        while(F--)
        {
            tot=0;
            scanf("%d%d%d",&N,&M,&W);
            rfup(i,1,M)
            {
                scanf("%d%d%d",&S,&E,&T);
                addEdge(S,E,T);
                addEdge(E,S,T);
            }
            rfup(i,1,W)
            {
                scanf("%d%d%d",&S,&E,&T);
                addEdge(S,E,-T);
            }
            if(bellman_ford()) printf("YES\n");
            else printf("NO\n");
        }
        return 0;
    }

[Link 1]: http://poj.org/problem?id=3259