用SPFA判断负权图

发布时间 2023-05-17 09:33:03作者: 匿名人士W

#include <bits/stdc++.h>
using namespace std;
const int N = 100010, M = 200010, INF = 0x3f3f3f3f;
#define ll long long
int e[N], ne[N], h[N], w[N], d[N], cnt[N], idx = 1;
int n, m;
bool st[N]; // 记录是否在队列里
void add (int a, int b, int c) {
  e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}
bool spfa() {

/*关于为什么用SPFA判断负权图时不用初始化d数组到无穷大的理解:

1. 构造一个虚拟节点 O,单向指向所有的节点,且到所有节点距离为0;(也就是超级源点, 之前也做过一道用超级源点的图论题,,,在哪来着。。。。)
2. 新图是否有负环等价于原始的图。
3.dist数组一开始为0,没有违背算法过程,可以理解为根据算法已经从O 更新到了各个节点,接下来的代码就是顺理成章。所以dist数组从所有为0的状态开始是有对应意义的。就是先走一步。
*/
  queue <int> q;
  for (int i = 1; i <= n; ++ i) q.push(i), st[i] = 1;
  while (!q.empty()) {
    int t = q.front(); q.pop();
    st[t] = 0;
    for (int i = h[t]; i; i = ne[i]) {
      int j = e[i];
      if (d[j] > d[t] + w[i]) {
        d[j] = d[t] + w[i];
        cnt[j] = cnt[t] + 1;
        if (cnt[j] >= n) return 1;
        if (!st[j]) {
          q.push(j);
          st[j] = 1;
        }
      }
    }
  }
  return 0;
}
int main(){
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  cin >> n >> m;
  while (m -- ) {
    int a, b, c;
    cin >> a >> b >> c;
    add(a, b, c);
  }
  int ans = spfa();
  if (spfa()) cout << "Yes";
  else cout << "No";
  return 0;
}