本文共 1639 字，大约阅读时间需要 5 分钟。

为了确定给定有向图中是否存在负权回路，我们将使用优化的Bellman-Ford算法。这个算法通过松弛边并跟踪距离来检测是否存在可能的负权回路。

方法思路

Bellman-Ford算法的标准实现复杂度为O(mn)，其中m是边数，n是节点数。在这个问题中，n=2000，m=10000的复杂度可能存在一定的挑战。因此，我们将采用队列优化后的就近逼近Floyd算法（SPFA），该算法在某些情况下表现优异。

解决代码

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;int n, m;int INF = 1e18;int d[n + 1];int cnt[n + 1];int h[n + 1];int ne[n + 1];int w[n + 1];int idx = 0;void add_edge(int u, int v, int w) { h[u] = idx; e[idx] = v; w[idx] = w; ne[idx] = h[u - 1]; idx++;}bool spfa() { for (int i = 1; i <= n; ++i) { d[i] = cnt[i] = INF; } queue
         
           q; for (int i = 1; i <= n; ++i) { d[i] = 0; q.push(i); cnt[i] = 0; } int update = n; while (q && update > 0) { int u = q.front(); q.pop(); for (int i = h[u]; i != -1; i = ne[i]) { int v = e[i], weight = w[i]; if (d[u] + weight < d[v]) { d[v] = d[u] + weight; if (cnt[v] > n) return true; cnt[v] = cnt[u] + 1; update--; if (d[v] < d[v]) { q.push(v); } } } } if (update <= 0) return false; return true;}int main() { scanf("%d %d", &n, &m); h[0] = -1; for (int i = 1; i < n; ++i) h[i] = -1; for (int i = 0; i < m; ++i) { int x, y, z; scanf("%d %d %d", &x, &y, &z); add_edge(x, y, z); } if (spfa()) { printf("Yes"); } else { printf("No"); }}
         
        
       
      
     
    
   

代码解释