首页 > 代码库 > 【模板】负环（spfa）

【模板】负环（spfa）

2024-09-23 19:29:46   203人阅读

洛谷——P3385 【模板】负环

题目描述

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

输入输出格式

输入格式：

 

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

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

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

 

输出格式：

 

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

 

输入输出样例

输入样例#1：
23 41 2 21 3 42 3 13 1 -33 31 2 32 3 43 1 -8
输出样例#1：
N0YE5

说明

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

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

bfs spfa判负环的代码：

int spfa1(int s){    memset(dis,0x3f,sizeof(dis));    memset(vis,false,sizeof(vis));    queue<int>q;    dis[s]=0,vis[s]=true;    q.push(s);    while(!q.empty())    {        int x=q.front();        q.pop();vis[x]=false;        for(int i=head[s];i;i=edge[i].next)        {            if(dis[x]+edge[i].ds<dis[edge[i].to])            {                dis[edge[i].to]=dis[x]+edge[i].ds;                sum[edge[i].to]++;                q.push(edge[i].to);                if(sum[edge[i].to]>n) return 1;              }        }    }    return 0;}

显然，这样是不对的，（不然我早就给全代码了！）这样会超时，全部TLE

这个题的正确是思路一个广搜的spfa。

来，看看代码（代码中我会给出各步骤原因）

技术分享

哎，终于很不容易的a了

#include<cstdio>#include<cstdlib>#include<cstring>#include<iostream>#include<algorithm>#define N 200003using namespace std;int t,n,m,x,y,z,tot,dis[N],head[N];bool vis[N],vist;struct Edge{    int ds,to,next;}edge[N<<1];void begin(){    memset(dis,0,sizeof(dis));    memset(head,0,sizeof(head));    memset(vis,false,sizeof(vis));    tot=vist=0;}void add(int from,int to,int dis){    tot++;    edge[tot].to=to;    edge[tot].ds=dis;    edge[tot].next=head[from];    head[from]=tot;}int read(){    int x=0,f=1;    char ch=getchar();    while(ch<‘0‘||ch>‘9‘)    {        if(ch==‘-‘) f=-1;        ch=getchar();            }    while(ch<=‘9‘&&ch>=‘0‘)    {        x=x*10+ch-‘0‘;        ch=getchar();    }    return x*f;}void spfa(int s){    vis[s]=true;    for(int i=head[s];i;i=edge[i].next)    {        int x=edge[i].to;        if(dis[s]+edge[i].ds<dis[x])        {            dis[x]=dis[s]+edge[i].ds;            if(vis[x]||vist)            {                vist=true;                break;            }            spfa(x);        }    }    vis[s]=false;}int main(){    t=read();    while(t--)    {        n=read(),m=read();        begin();        for(int i=1;i<=m;i++)        {            x=read(),y=read(),z=read();            add(x,y,z);            if(z>=0) add(y,x,z);        }        for(int i=1;i<=n;i++)        {            spfa(i);            if(vist) break;        }        if(vist) printf("YE5\n");        else printf("N0\n");    }    return 0;}

 

【模板】负环（spfa）


联系
我们