题目描述

给定一个 n 个点的有向图，请求出图中是否存在从顶点 1 出发能到达的负环。

负环的定义是：一条边权之和为负数的回路。

输入格式

输入的第一行是一个整数 T，表示测试数据的组数。对于每组数据的格式如下：

第一行有两个整数，分别表示图的点数 n 和接下来给出边信息的条数 m。

接下来 m 行，每行三个整数 u, v, w。

• 若 w≥0，则表示存在一条从 u 至 v 边权为 w 的边，还存在一条从 v 至 u 边权为 w 的边。
• 若 w < 0，则只表示存在一条从 u 至 v 边权为 w 的边。

输出格式

对于每组数据，输出一行一个字符串，若所求负环存在，则输出 YES，否则输出 NO。

输入输出样例

输入

2
3 4
1 2 2
1 3 4
2 3 1
3 1 -3
3 3
1 2 3
2 3 4
3 1 -8

输出

NO
YES

怎么判断负环呢

使用spfa跑一遍最短路,然后用一个数组cnt记录每个点的入队次数,入队次数大于了n,就是有负环,跑了一遍没找到,就没有

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
struct node{int to,dis;
};
int T;
vector<node>a[N];
int dis[N];
int vis[N];
int cnt[N];
int n,m;
queue<int>q;
bool spfa(){for(int i=1;i<=n;i++)dis[i]=2147483647;dis[1]=0;q.push(1);vis[1]=1;while(!q.empty()){int x=q.front();q.pop();vis[x]=0;for(int i=0;i<a[x].size();i++){int v=a[x][i].to;int w=a[x][i].dis;if(dis[v]>dis[x]+w){dis[v]=dis[x]+w;if(vis[v]==0){vis[v]=1;q.push(v);cnt[v]++;}if(cnt[v]>n)return true;}}}return false;
}
signed main(){scanf("%d",&T);while(T--){scanf("%d%d",&n,&m);memset(vis,0,sizeof(vis));memset(cnt,0,sizeof(vis));while(!q.empty())q.pop();for(int i=1;i<=n;i++)a[i].clear();for(int i=1;i<=m;i++){int u,v,w;scanf("%d%d%d",&u,&v,&w);a[u].push_back(node{v,w});if(w>=0)a[v].push_back(node{u,w});}if(spfa())printf("YES\n");else printf("NO\n");}
}