题目描述
暴力枚举/(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
说明
[nleq 2000
]
[mleq 3000
]
[-10000leq wleq 10000
]
[Tleq 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;
}