首页 > 代码库 > P3385 【模板】负环
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
一开始用差分约束中判断负环的方法，。
发现会T3个点，原因很是我们的SPFA 主要是用来求最短路，其次是用来判断负环。
所以很大的一部分时间用在了最短路上，
那么我们可以放弃最短路，直接求负环。
这样的话刚开始直接把所有的dis全部赋值为0即可
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<queue> 6 #include<algorithm> 7 #define lli long long int 8 using namespace std; 9 const int MAXN=200001;10 const int maxn=0x7fffff;11 inline void read(int &n)12 {13 char c=‘+‘;int x=0;bool flag=0;14 while(c<‘0‘||c>‘9‘)15 {c=getchar();if(c==‘-‘)flag=1;}16 while(c>=‘0‘&&c<=‘9‘)17 {x=(x<<1)+(x<<3)+c-48;c=getchar();}18 flag==1?n=-x:n=x;19 }20 int T,n,m;21 struct node22 {23 int u,v,w,nxt;24 }edge[MAXN*2];25 int head[MAXN];26 int num=1;27 int dis[MAXN];28 bool vis[MAXN];29 bool flag=0;30 inline void cler()31 {32 /*for(int i=1;i<=n;i++)33 {34 head[i]=-1;35 dis[i]=maxn;36 vis[i]=0;37 }*/38 memset(head,-1,sizeof(head));39 memset(dis,0,sizeof(dis));40 memset(vis,0,sizeof(vis));41 // dis[1]=0;42 flag=0;43 num=1;44 }45 inline void add_edge(int x,int y,int z)46 {47 edge[num].u=x;48 edge[num].v=y;49 edge[num].w=z;50 edge[num].nxt=head[x];51 head[x]=num++;52 }53 inline void SPFA(int now)54 {55 vis[now]=1;56 for(int i=head[now];i!=-1;i=edge[i].nxt)57 {58 if(dis[edge[i].v]>dis[edge[i].u]+edge[i].w)59 {60 61 if(vis[edge[i].v]||flag)62 {63 flag=1;64 break;65 }66 dis[edge[i].v]=dis[edge[i].u]+edge[i].w; 67 SPFA(edge[i].v);68 }69 }70 vis[now]=0;71 }72 int main()73 {74 read(T);75 while(T--)76 {77 //read(n);read(m);78 scanf("%d%d",&n,&m);79 cler();80 for(int i=1;i<=m;i++)81 {82 int x,y,z;83 scanf("%d%d%d",&x,&y,&z);84 //read(x);read(y);read(z);85 add_edge(x,y,z);86 if(z>=0)87 add_edge(y,x,z);88 }89 for(int i=1;i<=n;i++)90 {91 SPFA(i);92 if(flag) 93 break;94 }95 if(flag)printf("YE5\n"); 96 else printf("N0\n");97 }98 return 0;99 }
P3385 【模板】负环
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。