找负环（图论基础）

负环

环内路径上的权值和为负。

spfa找负环

两种基本的方法

1. 统计每一个点的入队次数，如果一个点入队了n次，则说明存在负环
2. 统计当前每个点中的最短路中所包含的边数，如果当前某个点的最短路所包含的边数大于等于n，也说明存在负环

实际上两种方法是等价的，都是判断是否路径包含n条边，$n$条边的话就有$n+1$个点
用的更多的还是第二种方法。

方法一

$cnt[x]:表示x的入队次数$

#include <bits/stdc++.h> 
#define int long long
#define rep(i,a,b) for(int i = (a); i <= (b); ++i)
#define fep(i,a,b) for(int i = (a); i >= (b); --i)
#define pii pair<int, int>
#define ll long long
#define db double
#define endl '\n'
#define x first
#define y second
#define pb push_back
#define inf 0x3f3f3f3f*1llusing namespace std;void solve()
{int n,m1,m2;cin>>n>>m1>>m2;vector<vector<pii>>g(n+1);rep(i,1,m1){int u,v,w;cin>>u>>v>>w;g[u].pb({v,w});g[v].pb({u,w});}	rep(i,1,m2){int u,v,w;cin>>u>>v>>w;g[u].pb({v,-w});}vector<int>inq(n+1,0);vector<int>cnt(n+1,0);vector<int>d(n+1,0);queue<int>q;rep(i,1,n){q.push(i);inq[i]=1;}while(q.size()){auto t=q.front();q.pop();int u=t;inq[u]=0;for(auto it:g[u]){int v=it.x,w=it.y;if(d[v]>d[u]+w){d[v]=d[u]+w;if(!inq[v]){q.push(v);inq[v]=1;cnt[v]++;if(cnt[v]>=n){cout<<"YES"<<endl;return;}}}}}cout<<"NO"<<endl;
}signed main(){ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//   	freopen("1.in", "r", stdin);int _;cin>>_;while(_--)solve();return 0;
}

方法二

$cnt[x]:表示从起点到x所经过的最短路径的边数$

#include <bits/stdc++.h> 
#define int long long
#define rep(i,a,b) for(int i = (a); i <= (b); ++i)
#define fep(i,a,b) for(int i = (a); i >= (b); --i)
#define pii pair<int, int>
#define ll long long
#define db double
#define endl '\n'
#define x first
#define y second
#define pb push_back
#define inf 0x3f3f3f3f*1llusing namespace std;void solve()
{int n,m1,m2;cin>>n>>m1>>m2;vector<vector<pii>>g(n+1);rep(i,1,m1){int u,v,w;cin>>u>>v>>w;g[u].pb({v,w});g[v].pb({u,w});}	rep(i,1,m2){int u,v,w;cin>>u>>v>>w;g[u].pb({v,-w});}vector<int>inq(n+1,0);vector<int>cnt(n+1,0);vector<int>d(n+1,0);queue<int>q;rep(i,1,n){q.push(i);inq[i]=1;}while(q.size()){auto t=q.front();q.pop();int u=t;inq[u]=0;for(auto it:g[u]){int v=it.x,w=it.y;if(d[v]>d[u]+w){d[v]=d[u]+w;cnt[v]=cnt[u]+1;if(cnt[v]>=n){cout<<"YES"<<endl;return;}if(!inq[v]){q.push(v);inq[v]=1;}}}}cout<<"NO"<<endl;
}signed main(){ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//   	freopen("1.in", "r", stdin);int _;cin>>_;while(_--)solve();return 0;
}

实际效果

方法一跑出来的结果是$1024ms$
方法二跑出来的结果是$671ms$