洛谷2850 【Usaco2006 Dec】虫洞Wormholes SPFA

本是古典何须时尚 2021-09-30 15:48 218阅读 0赞

**问题描述**

John在他的农场中闲逛时发现了许多虫洞。虫洞可以看作一条十分奇特的有向边，并可以使你返回到过去的一个时刻（相对你进入虫洞之前）。John的每个农场有M条小路（无向边)连接着N （从1..N标号）块地，并有W个虫洞。其中1<=N<=500,1<=M<=2500,1<=W<=200。 现在John想借助这些虫洞来回到过去（出发时刻之前），请你告诉他能办到吗。 John将向你提供F(1<=F<=5)个农场的地图。没有小路会耗费你超过10000秒的时间，当然也没有虫洞回帮你回到超过10000秒以前。

spfa判负环，以前写spfa都是bfs，这次看了看黄学长的dfs的spfa，感觉写起来也是很简单的。

只要看dfs外的点是否有回来更新它就可以了。

注意虫洞是单向边，小路是双向边。

// 虫洞 spfa判负环 
    #include<bits/stdc++.h>
    using namespace std;
    int T,n,m,W,cnt;
    int head[505],dis[505];
    bool vis[505],flag;
    struct edge{
        int next,to,w;
    }e[100001];
    inline int read(){
        int x=0,f=1;char ch=getchar();
        while(ch>'9'||ch<'0'){
        if(ch=='-')f=-1;ch=getchar();}
        while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
        return x*f;
    }
    void ins(int u,int v,int w)
    {e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;e[cnt].w=w;}
    void insert(int u,int v,int w){
        ins(u,v,w);ins(v,u,w);
    }
    void spfa(int x){
        vis[x]=1;
        for(int i=head[x];i;i=e[i].next){
            int s=e[i].to;
            if(dis[s]>dis[x]+e[i].w){
                
                if(vis[s]){flag=1;return;}
                else{
                    dis[s]=dis[x]+e[i].w;
                    vis[s]=1;
                    spfa(s);
                }
            }
        }
        vis[x]=0;
    }
    bool judge(){
        memset(dis,0,sizeof dis);
        memset(vis,0,sizeof vis);
        flag=0;
        for(int i=1;i<=n;i++){
            spfa(i);
            if(flag)return 1;
        }
        return 0;
    }
    int main(){
        scanf("%d",&T);
        while(T--){
            n=read();m=read();W=read();
            int u,v,w;
            memset(head,0,sizeof head);
            for(int i=1;i<=m;i++){
                u=read();v=read();w=read();
                insert(u,v,w);
            }
            for(int i=1;i<=W;i++){
                u=read();v=read();w=read();
                ins(u,v,-w);
            }
            if(judge())printf("YES\n");
            else printf("NO\n");
        }
        return 0;
    }

转载于:https://www.cnblogs.com/Elfish/p/7648798.html