[关闭]
@zzzc18 2017-11-09T08:51:36.000000Z 字数 965 阅读 404

SPFA判负环

模板库


地址

深搜版 :如果更新 的时候两次经过一个点,那么一定有负环

  1. #include<bitset>
  2. #include<cstdio>
  3. #include<cstring>
  4. #include<algorithm>
  5. using namespace std;
  6. const int MAXN = 200000+9;
  7. const int MAXM = 200000+9;
  8. struct E{
  9. int next,to;
  10. int val;
  11. }edge[MAXM<<1];
  12. int head[MAXN],edge_num;
  13. int n,m;
  14. bool pd;
  15. bitset<MAXN> vis;
  16. int dis[MAXN];
  17. void addedge(int x,int y,int v){
  18. edge[++edge_num].next=head[x];
  19. edge[edge_num].to=y;
  20. edge[edge_num].val=v;
  21. head[x]=edge_num;
  22. }
  23. void SPFA(int x){
  24. if(pd)return;
  25. vis[x]=1;
  26. for(int i=head[x];i;i=edge[i].next){
  27. if(pd)return;
  28. if(dis[x]+edge[i].val<dis[edge[i].to]){
  29. dis[edge[i].to]=dis[x]+edge[i].val;
  30. if(vis[edge[i].to]){
  31. pd=1;
  32. return;
  33. }
  34. SPFA(edge[i].to);
  35. }
  36. }
  37. vis[x]=0;
  38. }
  39. void solve(){
  40. for(int i=1;i<=n;i++){
  41. SPFA(i);
  42. if(pd){puts("YE5");return;}
  43. }
  44. puts("N0");
  45. }
  46. int main(){
  47. int kase;
  48. scanf("%d",&kase);
  49. while(kase--){
  50. memset(head,0,sizeof(head));
  51. vis.reset();
  52. memset(dis,0,sizeof(dis));
  53. edge_num=0;
  54. pd=0;
  55. scanf("%d%d",&n,&m);
  56. for(int i=1;i<=m;i++){
  57. int a,b,c;
  58. scanf("%d%d%d",&a,&b,&c);
  59. addedge(a,b,c);
  60. if(c>=0)addedge(b,a,c);
  61. }
  62. solve();
  63. }
  64. return 0;
  65. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注