思路:
运用 SPFA算法 结合 抽屉原理 判断图中是否存在负环
时间复杂度:
O(nm) n
表示点数,m
表示边数
代码:
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int N = 2000+10;
const int M = 10000+10;
#define inf 0x3f3f3f3f
int h[M],e[M],ne[M],w[M],idx; // 邻接表存储所有边
int dist[N],cnt[N]; // dist[x]存储1号点到x的最短距离,cnt[x]存储1到x的最短路中经过的点数
bool st[N];// 存储每个点是否在队列中
int x,y,z,n,m;
void add(int x,int y,int z)
{
e[idx]=y,ne[idx]=h[x],h[x]=idx,w[idx]=z,idx++;
}
// 如果存在负环,则返回true,否则返回false。
bool spfa()
{
// 不需要初始化dist数组
// 原理:如果某条最短路径上有n个点(除了自己),那么加上自己之后一共有n+1个点,由抽屉原理一定有两个点相同,所以存在环。
queue<int> q;
for(int i=1;i<=n;i++)
{
q.push(i);
st[i]=true;
}
while(!q.empty())
{
int t=q.front();
q.pop();//队头t弹出了,置为false,表示不在队列中
st[t]=false;
for(int i=h[t];i!=-1;i=ne[i])
{
int b=e[i];
if(dist[b]>dist[t]+w[i])
{
dist[b]=dist[t]+w[i];
cnt[b]=cnt[t]+1;
if(cnt[b]>=n) return true;//某次cnt[x]>=n表示1到x经过了至少n条边,n+1个点(包括自己),由抽屉原理可知有两个点值相同,存在负环
if(!st[b])//如果更新的点b不在队列中,才把它加到队列中去
{
q.push(b);
st[b]=true;
}
}
}
}
return false;
}
int main()
{
cin.tie(0);
ios::sync_with_stdio(false);
memset(h,-1,sizeof h);
cin>>n>>m;
while (m -- )
{
cin>>x>>y>>z;
add(x,y,z);
}
if(spfa()) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
return 0;
}