poj----Wormholes 小咪咪 2022-06-16 00:26 124阅读 0赞 #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxx=99999999; int t,n,m,l,k; struct A { int s,e,v; } f[5205]; int dis[505]; bool bellman_ford() { bool flag; int i=0; for(i=1;i<=n;i++){ dis[i] = maxx; }//因为只是判断是否有负环，所以dis[i]数组赋不赋值也都无所谓了，但是要是求最短路径的话就必须赋值 dis[1]=0; // for(i=0;i<10;i++) // printf("%d ",dis[i]); for(i=1; i<=n; i++) { flag=false; for(int j=0; j<k; j++) { if(dis[f[j].e]>dis[f[j].s]+f[j].v) { dis[f[j].e]=dis[f[j].s]+f[j].v; flag=true; } } //每条边进行|V|-1次松弛后，检查是否存在负环并返回相应的布尔值， //因为进行|V|-1次松弛后若没有负环则v.d的值确定不变， //若有负环则会继续进行松弛操作，因为一个数+负数是一定比它本身要小的。 //总之就是：有负环松弛操作就会继续，没负环松弛操作就会停止 if(!flag) break;//也可以直接就返回false，因为flag为false就说明不在松弛了， //也就是说不存在负环，但是后面还是得在判断一次，因为有可能刚好最后一次可以松弛 //从而使得flag为true. } if(i==n+1)//判断松弛操作是否还在继续，还在继续就存在负环咯 return true; else return false; } int main() { int a,b,c; scanf("%d",&t); while(t--) { k=0; scanf("%d %d %d",&n,&m,&l); for(int i=0; i<m; i++) { scanf("%d %d %d",&a,&b,&c); f[k].s=a; f[k].e=b; f[k++].v=c; f[k].s=b; f[k].e=a; f[k++].v=c; } for(int i=0; i<l; i++) { scanf("%d %d %d",&a,&b,&c); f[k].s=a; f[k].e=b; f[k++].v=-c; } //printf("%d\n",k); if(bellman_ford())//bug你藏得好深，找啊找，找的我想哭，把函数bellman_ford()写成了bellman_ford，我也是醉了，想死的心都有了，你为何如此待我，我容易吗我。aaaaaaaaaaaaaaaaaaa............. printf("YES\n"); else printf("NO\n"); } return 0; }
还没有评论，来说两句吧...