洛谷 P3385 【模板】负环

P3385 【模板】负环

题目描述

暴力枚举/SPFA/Bellman-ford/奇怪的贪心/超神搜索

输入输出格式

输入格式：

 

第一行一个正整数T表示数据组数，对于每组数据：

第一行两个正整数N M，表示图有N个顶点，M条边

接下来M行，每行三个整数a b w，表示a->b有一条权值为w的边（若w<0则为单向，否则双向）

 

输出格式：

 

共T行。对于每组数据，存在负环则输出一行"YE5"(不含引号)，否则输出一行"N0"(不含引号)。

 

输入输出样例

输入样例#1： 复制

2
3 4
1 2 2
1 3 4
2 3 1
3 1 -3
3 3
1 2 3
2 3 4
3 1 -8

输出样例#1： 复制

N0
YE5

说明

N,M,|w|≤200 000；1≤a,b≤N；T≤10 建议复制输出格式中的字符串。

此题普通Bellman-Ford或BFS-SPFA会TLE

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define MAXN 200010
using namespace std;
int T,n,m,tot,vist;
int vis[MAXN],head[MAXN],dis[MAXN];
int to[MAXN*2],cap[MAXN*2],net[MAXN*2];
int add(int u,int v,int w){
    to[++tot]=v;cap[tot]=w;net[tot]=head[u];head[u]=tot;
}
int spfa(int now){
    vis[now]=1;
    for(int i=head[now];i;i=net[i])
        if(dis[to[i]]>dis[now]+cap[i]){
            dis[to[i]]=dis[now]+cap[i];
            if(vis[to[i]]||spfa(to[i])){
                vis[to[i]]=0;
                return 1;
            }
        }
    vis[now]=0;
    return 0;
}
int main(){
    //freopen("a.in","r",stdin);
    scanf("%d",&T);
    while(T--){
        tot=0;vist=0;
        memset(to,0,sizeof(to));
        memset(cap,0,sizeof(cap));
        memset(net,0,sizeof(net));
        memset(dis,0,sizeof(dis));
        memset(vis,0,sizeof(vis));
        memset(head,0,sizeof(head));
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;i++){
            int x,y,z;
            scanf("%d%d%d",&x,&y,&z);
            add(x,y,z);
            if(z>0) add(y,x,z);
        }
        for(int i=1;i<=n;i++)
            if(spfa(i)){
                cout<<"YE5"<<endl;
                vist=1;
                break;
            }
        if(!vist) cout<<"N0"<<endl;
    }
    return 0;
}