利用Bellman-Ford算法（有向图）判断负环

「爱情、让人受尽委屈。」 2023-07-12 05:05 22阅读 0赞

1 // 根据Bellman-Ford算法的原理
      2 // 判断负环（算法的最大更新次数，应该是顶点数-1次）
      3 // 而如果存在负环，算法会一直更新下去
      4 
      5 // 我们根据循环进行的次数，来判断负环
      6 
      7 #include <iostream>
      8 #include <cstdio>
      9 #include <cstring>
     10 
     11 using namespace std;
     12 
     13 const int max_N=1000+2;
     14 const int max_E=10000+2;
     15 
     16 int N,E;
     17 
     18 struct edge
     19 {
     20     int from,to,cost;
     21 };
     22 edge es[max_E];
     23 
     24 int d[max_N];
     25 
     26 void solve()
     27 {
     28     memset(d,0,sizeof(d));
     29     int cnt=0;
     30     while(cnt<N)
     31     {
     32         bool update=false;
     33         for(int i=0;i<E;++i)
     34         {
     35             edge e=es[i];
     36             if(d[e.to]>d[e.from]+e.cost)
     37             {
     38                 printf("hei  ");
     39                 d[e.to]=d[e.from]+e.cost;
     40                 update=true;
     41             }
     42         }
     43         if(update==false)
     44         {
     45             printf("NO\n");
     46             break;
     47         }
     48         else
     49         {
     50             ++cnt;
     51             if(cnt==N)
     52             {
     53                 printf("YES\n");
     54                 break;
     55             }
     56         }
     57     }
     58 }
     59 
     60 int main()
     61 {
     62     scanf("%d %d",&N,&E);
     63     for(int i=0;i<E;++i)
     64     {
     65         scanf("%d%d%d",&es[i].from,&es[i].to,&es[i].cost);
     66     }
     67     solve();
     68     return 0;
     69 }
     70 
     71 /*
     72 7 10
     73 0 1 2
     74 0 2 5
     75 1 2 4
     76 1 3 6
     77 1 4 10
     78 2 3 2
     79 3 5 1
     80 4 5 3
     81 4 6 5
     82 5 6 9
     83 NO
     84 */
     85 
     86 /*
     87 3 3
     88 0 1 1
     89 1 2 2
     90 2 1 -2
     91 NO
     92 */
     93 
     94 /*
     95 3 3
     96 0 1 1
     97 1 2 2
     98 2 1 -3
     99 
    100 */