所需知识

将所有点不形成环的情况下随意连接，最多可以生成n-1条边.

算法1

假设有n个点，为了不生成负环，所以负权边最多可以存在n-1条，但是如果存在负环，经过负环的无数次累加，必然维护次数会超出n-1，所以总结一下就是：
若存在负环边，维护次数必定大于n-1;
若不存在负环边，维护次数必定小于等于n-1.
那么这个算法的总维护次数绝对不超n次!

时间复杂度

O(n)

C++ 代码

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
const int N=1e5+10;
int h[N],e[N],w[N],ne[N],idx = 1,sta[N];
int dis[N];
int cnt=0;
queue<int> q;
void insert(int x,int y,int z){
    ne[idx] = h[x];
    h[x] = idx;
    e[idx] = y;
    w[idx++] = z;
}
bool spfa(int n){
    for(int i=1;i<=n;i++){
        q.push(i);
        sta[i] = true;
    }
    while(q.size()){
        int u = q.front();
        sta[u] = false;
        q.pop();
        for(int i=h[u];i;i = ne[i]){
            int temp = e[i];
            if(dis[temp] > dis[u] + w[i]){
                dis[temp] = dis[u] + w[i];
                if(!sta[temp]){
                    if(++cnt>n - 1) return true;//变动一下这里就行了
                    q.push(temp);
                    sta[temp] = true;
                }
            }
        }
    }
    return false;
}
int main(){
    int n,m;
    cin>>n>>m;
    int x,y,z;
    while(m--){
        cin>>x>>y>>z;
        insert(x,y,z);
    }
    if(spfa(n)) cout<<"Yes";
    else cout<<"No";
}