【模板】负环
题目描述
给定一个 n n n 个点的有向图,请求出图中是否存在从顶点 1 1 1 出发能到达的负环。
负环的定义是:一条边权之和为负数的回路。
输入格式
本题单测试点有多组测试数据。
输入的第一行是一个整数 T T T,表示测试数据的组数。对于每组数据的格式如下:
第一行有两个整数,分别表示图的点数 n n n 和接下来给出边信息的条数 m m m。
接下来 m m m 行,每行三个整数 u , v , w u, v, w u,v,w。
- 若 w ≥ 0 w \geq 0 w≥0,则表示存在一条从 u u u 至 v v v 边权为 w w w 的边,还存在一条从 v v v 至 u u u 边权为 w w w 的边。
- 若 w < 0 w < 0 w<0,则只表示存在一条从 u u u 至 v v v 边权为 w w w 的边。
输出格式
对于每组数据,输出一行一个字符串,若所求负环存在,则输出 YES
,否则输出 NO
。
样例 #1
样例输入 #1
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
样例输出 #1
NO
YES
提示
数据规模与约定
对于全部的测试点,保证:
- 1 ≤ n ≤ 2 × 1 0 3 1 \leq n \leq 2 \times 10^3 1≤n≤2×103, 1 ≤ m ≤ 3 × 1 0 3 1 \leq m \leq 3 \times 10^3 1≤m≤3×103。
- 1 ≤ u , v ≤ n 1 \leq u, v \leq n 1≤u,v≤n, − 1 0 4 ≤ w ≤ 1 0 4 -10^4 \leq w \leq 10^4 −104≤w≤104。
- 1 ≤ T ≤ 10 1 \leq T \leq 10 1≤T≤10。
提示
请注意, m m m 不是图的边数。
AC代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int>PII;
const int N=2e5+10;
const int MOD = 998244353;
const int INF=0X3F3F3F3F;
const int dx[]={-1,1,0,0,-1,-1,+1,+1};
const int dy[]={0,0,-1,1,-1,+1,-1,+1};
const int M = 1e6 + 10;
//好累啊
//spfa算法求最短路时间复杂度最坏n * m
int n, m, s, t, f;
vector<PII>ed[N];
int dis[N];
queue<int>q;
bool st[N];
int cnt[N];
bool spfa()
{
memset(cnt, 0, sizeof cnt);
memset(dis, 0x3f, sizeof dis);
for(int i = 1; i <= m; i ++)
{
int u, v, w;
cin >> u >> v >> w;
if(w >= 0)
{
ed[u].push_back({v, w});
ed[v].push_back({u, w});//因为是无向图
}
else {
ed[u].push_back({v, w});
}
}
for(int i = 1; i <= n; i ++) st[i] = false;
dis[1] = 0;
st[1] = true;
q.push(1);
cnt[1] ++;
while(!q.empty()){
int x = q.front();
q.pop();
st[x] = false;
for(auto it : ed[x])
{
if(dis[it.first] <= dis[x] + it.second) continue;
dis[it.first] = dis[x] + it.second;
if(!st[it.first])
{
cnt[it.first] ++;
st[it.first] = true;
q.push(it.first);
if(cnt[it.first] >= n) return true;
}
}
}
return false;
}
int main()
{
int t;
cin >> t;
while(t --){
f = 0;
cin >> n >> m ;//起点跟终点
if(spfa()) puts("YES");
else puts("NO");
for(int i = 0; i <= n; i ++)
{
ed[i].clear();
}
}
return 0;
}