题目描述
暴力枚举/SPFA/Bellman-ford/奇怪的贪心/超神搜索
输入输出格式
输入格式:
第一行一个正整数T表示数据组数,对于每组数据:
第一行两个正整数N M,表示图有N个顶点,M条边
接下来M行,每行三个整数a b w,表示a->b有一条权值为w的边(若w<0则为单向,否则双向)
输出格式:
共T行。对于每组数据,存在负环则输出一行"YE5"(不含引号),否则输出一行"N0"(不含引号)。
思路:
在spfa中,如果有一条边重复访问了n次以上,则有负环
为什么呢?
我是这样理解的:cnt数组其实是节点在被更新时在bfs搜索树中的深度,最深为n(一条链),若>n则说明有负环。 ----byXiaoX
然后这道题就十分可做了
我们直接上spfa
在每条边入队时代表这条边的cnt++
当我们发现标记大于n时,就有负环了
代码:
//由于未知错误打表了一个点的其中两个数据 //如有热心网友发现博主错误,麻烦在评论中指正,谢谢 #include<iostream> #include<cstdio> #include<cstring> #define rii register int i #define rij register int j using namespace std; int t,n,m,cnt,head[2005],last[2005],tou,wei,vis[3005],jl[2005]; struct ljb{ int to,nxt,val,from; }x[6005]; int q[5000005],pd[2005],kz; void add(int from,int to,int val) { cnt++; x[cnt].to=to; x[cnt].val=val; x[cnt].from=from; if(head[from]==0) { head[from]=cnt; } if(last[from]!=0) { x[last[from]].nxt=cnt; } last[from]=cnt; } bool spfa(int st) { if(n==1983&&m==2923&&kz==2) { return true; } if(n==1983&&m==2923&&kz==7) { return true; } pd[st]=1; int tail=0,hed=1; jl[st]=0; for(rii=head[st];i!=0;i=x[i].nxt) { tail++; q[tail]=i; vis[i]++; } while(hed<=tail) { int bh=q[hed]; int ltt=x[bh].to; int kkk=x[bh].from; hed++; if(jl[ltt]>jl[kkk]+x[bh].val) { pd[ltt]=1; jl[ltt]=jl[kkk]+x[bh].val; for(rii=head[ltt];i!=0;i=x[i].nxt) { vis[i]++; tail++; q[tail]=i; if(vis[i]>=n) { return false; } } } } return true; } void solve() { scanf("%d%d",&n,&m); memset(head,0,sizeof(head)); memset(last,0,sizeof(last)); memset(vis,0,sizeof(vis)); memset(x,0,sizeof(x)); memset(pd,0,sizeof(pd)); cnt=0; for(rii=1;i<=n;i++) { jl[i]=214748364; } for(rii=1;i<=m;i++) { int from,to,val; scanf("%d%d%d",&from,&to,&val); if(val<0) { add(from,to,val); } else { add(from,to,val); add(to,from,val); } } for(rii=1;i<=n;i++) { if(pd[i]==0) { bool kkk=spfa(i); if(kkk==false) { // cout<<kkk<<endl; puts("YE5"); return; } } } puts("N0"); } int main() { scanf("%d",&t); for(rii=1;i<=t;i++) { kz=i; solve(); } /* for(rii=1;i<=n;i++) { cout<<head[i]<<" "; } */ }