欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-04-10 22:01:47
题目链接 判断一张图中是否存在关于顶点1的负环: 可以用SPFA跑一遍,存在负环的情况就是点进队大于n次 因为在存在负环的情况下,SPFA会越跑越小,跑进死循环 在最差的情况下,存在的负环长度是“n+1个顶点”这么长 rt: 显然这是n个点长度,但不是环; 这就是一个环,n+1个点的长度; 所以代码 ......

题目链接

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

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

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

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

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

rt:

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

 

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

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

 

这就是一个环,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;//平淡的结束
}