洛谷P2850/USACO06DEC 虫洞Wormholes

@Pelom  October 31, 2019

题意

判负环

数据范围:$1 \le n \le 500,1 \le m \le 2500$

题解

$\text{dfs SPFA}$判负环即可

代码:

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=510;
const int M=5210;
struct edge{
    int nxt,to,w;
} e[M];
int f,n,m,w,a,b,c;
int cnt;
int head[N],dis[N];
bool vis[N];
inline void add(int u,int v,int w){
    e[++cnt]=(edge){head[u],v,w};
    head[u]=cnt;
}
bool SPFA(int u){
    vis[u]=1;
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(dis[v]>dis[u]+e[i].w){
            dis[v]=dis[u]+e[i].w;
            if(vis[v] || SPFA(v)){
                vis[u]=0;
                return 1;
            }
        }
    }
    vis[u]=0;
    return 0;
}
int main(){
    scanf("%d",&f);
    for(;f--;){
        cnt=0;
        memset(head,0,sizeof(head));
        memset(dis,0,sizeof(dis));
        scanf("%d%d%d",&n,&m,&w);
        for(int i=1;i<=m;i++){
            scanf("%d%d%d",&a,&b,&c);
            add(a,b,c);
            add(b,a,c);
        }
        for(int i=1;i<=w;i++){
            scanf("%d%d%d",&a,&b,&c);
            add(a,b,-c);
        }
        bool flag=0;
        for(int i=1;i<=n;i++)
            if(SPFA(i)){
                flag=1;
                break;
            }
        if(flag)
            puts("YES");
        else puts("NO");
    }
    return 0;
}

添加新评论