<题解>洛谷P3385 【模板】负环

题目链接

判断一张图中是否存在关于顶点1的负环:

可以用spfa跑一遍，存在负环的情况就是点进队大于n次

因为在存在负环的情况下,spfa会越跑越小，跑进死循环

在最差的情况下,存在的负环长度是“n+1个顶点”这么长

rt:

 

显然这是n个点长度,但不是环；

 

这就是一个环,n+1个点的长度;

所以代码很明了了,只需将一般spfa改动一点饥渴
code:

#include<bits/stdc++.h>万能头，懒得打很多头文件
using namespace std;
//数据是骗人的，要开大..
const int maxn=50001;
//基本的变量或者数组都是：
queue<int > q;
bool visited[maxn];
int head[maxn],cnt,js[maxn],dis[maxn];
struct ppap {
    int next,to,dis;
} edge[maxn];
int t,n,m;
//快读部分
int read() {
    bool f=0;
    char ch;
    int x=0;
    ch=getchar();
    while(ch>'9'||ch<'0') {
        if(ch=='-')
            f=!f;
        ch=getchar();
    }
    while(ch<='9'&&ch>='0') {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return !f?x:-x;
}
//链式前向星添边
void add(int from,int to,int dis) {
    edge[++cnt].next=head[from];
    head[from]=cnt;
    edge[cnt].to=to;
    edge[cnt].dis=dis;
}
//和常见spfa一样，在其中判断条件即可
bool spfa() {
    q.push(1);
    visited[1]=1;
    dis[1]=0;
    js[1]=1;
    while(!q.empty()) {
        int u=q.front();
        q.pop();
        visited[u]=0;
        for(int i=head[u]; i; i=edge[i].next) {
            int v=edge[i].to;
            if(dis[v]>dis[u]+edge[i].dis) {
                dis[v]=dis[u]+edge[i].dis;
                if(visited[v]==0) {
                    js[v]=js[u]+1;
                    if(js[v]>n) return true;
                    visited[v]=1;
                    q.push(v);
                }
            }
        }
    }
    return false;
}

int main() {
    t=read();
    while(t--) {
        n=read(),m=read();
        memset(head,0,sizeof head);
        memset(js,0,sizeof js);
        memset(edge,0,sizeof edge);
        memset(dis,0x3f,sizeof dis);
        memset(visited,0,sizeof visited);
        //初始化
        for(int i=1,a,b,w; i<=m; i++) {
            a=read(),b=read(),w=read();
            add(a,b,w);
            if(w>=0)
                add(b,a,w);
        }
        if(spfa()) cout<<"ye5"<<"\n";
        else cout<<"n0"<<"\n";
    }
    return 0;//平淡的结束
}