题目描述
暴力枚举/\(SPFA\)/\(Bellman-ford\)/奇怪的贪心/超神搜索
寻找一个从顶点1所能到达的负环，负环定义为：一个边权之和为负的环。
输入输出格式
输入格式
第一行一个正整数\(T\)表示数据组数，对于每组数据：
第一行两个正整数\(N\) \(M\)，表示图有\(N\)个顶点，\(M\)条边
接下来\(M\)行，每行三个整数\(a\) \(b\) \(w\)，表示\(a->b\)有一条权值为\(w\)的边（若\(w<0\)则为单向，否则双向）
输出格式
共\(T\)行。对于每组数据，存在负环则输出一行\("YE5"\)(不含引号)，否则输出一行\("N0"\)(不含引号)。
输入输出样例
输入样例#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
N0
YE5
说明
\[n\leq 2000
\]
\]
\[m\leq 3000
\]
\]
\[-10000\leq w\leq 10000
\]
\]
\[T\leq 10
\]
\]
建议复制输出格式中的字符串。
本题数据感谢\(@negiizhao\)的精心构造，请不要使用玄学算法
本题数据有更新
题解
由题意得：负环就是一个边权之和为负的环。
由于\(Dijkstra\)算法不能求解带有负权边的图，因此我们就使用\(SPFA\)算法求解。(题目不是说了吗)
接下来，就是套用\(SPFA\)算法模板的时间了！
如何判定负环呢？
根据负环的定义，我们可以设\(cnt[x]\)表示从\(1\)到\(x\)的最短路径包含的边数，初始化\(cnt[1]=0\)。
当执行\(dis[y] = dis[x] + z\)时，\(cnt[y] = cnt[x] + 1\)。
若此时发现\(cnt[y] ≥n\)，就说明图中有负环。
若算法正常结束，就说明图中没有负环。
代码
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cctype>
#include <queue>
using namespace std;
inline int gi()
{
int f = 1, x = 0; char c = getchar();
while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar();}
while (c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar();}
return f * x;
}
int ver[10005], nxt[10005], head[10005], e[10005], tot;
int n, m, ans, vis[10005], dis[10005], cnt[10005];
int u = 1;
inline void add(int u, int v, int w)
{
ver[++tot] = v, e[tot] = w, nxt[tot] = head[u], head[u] = tot;
}//邻接表存图
inline bool SPFA()
{
queue <int> q;
memset(dis, 0x3f3f3f3f, sizeof(dis));
memset(vis, 0, sizeof(vis));
vis[u] = 1, dis[u] = 0, cnt[u] = 1;
q.push(u);
while (!q.empty())
{
int x = q.front(); q.pop();
vis[x] = 0;
for (int i = head[x]; i; i = nxt[i])
{
int y = ver[i], z = e[i];
if (dis[y] > dis[x] + z)
{
dis[y] = dis[x] + z;
cnt[y] = cnt[x] + 1;
if (cnt[y] > n) return true;//有负环
if (!vis[y])
{
vis[y] = 1; q.push(y);
}
}
}
}
return false;
}
//以上为SPFA算法
int main()
{
int t = gi();
while (t--)
{
tot = 0;
memset(cnt, 0, sizeof(cnt));
memset(head, 0, sizeof(head));//多测要清空
n = gi(), m = gi();
for (int i = 1; i <= m; i++)
{
int x = gi(), y = gi(), z = gi();
add(x, y, z);
if (z >= 0)//是双向边
{
add(y, x, z);
}
}
if (SPFA()) puts("YE5");//图中有负环
else puts("N0");//没有负环
}
return 0;
}