本编标红字段均是值得纳为己用的经验条~
引言：
此前，我们已经学习了Bellman-Ford算法与spfa算法，这两个算法都是可以处理边权有负数的情况，此外，他俩还有个妙用，就是判断图中是否存在负环。
本篇就是介绍他俩怎么判断负环的。
判断负环的代码与他本身的代码都是大差不差的，下文细细品鉴~~
Bellman-Ford算法判断负环：
BF算法是暴力过 n – 1 轮、单趟全遍历边进行的松弛操作，他的最差情况就是至多会进行 n – 1 轮松弛操作，到第 n 轮肯定是松弛不了的，能松弛的就一定存在负环。所以我们就可以用标记变量 bool flag 来特判经过第 n 轮之后的状态，当然这个flag也可以是当作优化的，提前结束，省去不必要的轮。
这个BF算法其实只关心边，所以也可以用一个结构体存边的信息，就不用存图了，这里我们也来练习一下~
OJ题来源：洛谷
OJ题名：【模板】负环
OJ题归属：图论基础【单源最短路】
解题算法：结构体存边信息 + Bellman-Ford算法判断负环
#include<iostream>
#include<cstring>
using namespace std;
const int N = 2e3 + 10, M = 3e3 + 10;
int n, m;
int pos;
struct node
{
int x, y, z;
}e[M * 2];
int dist[N];
bool bf()
{
// 初始化
memset(dist, 0x3f3f3f3f, sizeof dist);
dist[1] = 0;
bool flag;
// 执行 n 轮松弛操作，看最后一轮结束后的结果
for (int i = 1; i <= n; i++)
{
flag = false;
for (int j = 1; j <= pos; j++)
{
int u = e[j].x, v = e[j].y, w = e[j].z;
if (dist[u] == 0x3f3f3f3f) continue;
if (dist[u] + w < dist[v])
{
dist[v] = dist[u] + w;
flag = true;
}
}
// 这步是做的优化
if (flag == false) return flag;
}
return flag;
}
int main()
{
int T; cin >> T;
while (T–)
{
cin >> n >> m;
pos = 0;
for (int i = 1; i <= m; i++)
{
int u, v, w; cin >> u >> v >> w;
pos++;
e[pos].x = u, e[pos].y = v, e[pos].z = w;
if (w >= 0)
{
pos++;
e[pos].x = v, e[pos].y = u, e[pos].z = w;
}
}
if (bf()) cout << "YES" << endl;
else cout << "NO" << endl;
}
return 0;
}
spfa 算法判断负环：
spfa 算法是用队列优化的BF算法。
存在负环时，while循环会死循环，我们可以计数的方式，既可以判断负环，也可以跳出死循环。
计数的方式—>小动态规划：每个节点配一个 cnt 数组；cnt[i] 表示从起点到 i 位置经过多少条边；cnt[i] > n – 1 即存在负环，cnt[i] <= n – 1 有最短路，没有负环。
状态转移方程：起点 ………………….u——v 此时我们来算cnt[v]，它等于刚刚经过的一条边加上在这条边之前所经过的边个数，这个在cnt[u]里面存着，即 cnt[v] = cnt[u] + 1。
#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
typedef pair<int, int> PII;
const int N = 2e3 + 10;
int n, m;
vector<PII> edges[N];
int dist[N];
bool st[N]; // 标记哪些点在队列里面
int cnt[N];
bool spfa()
{
// 初始化 — 既是初始化也是清理数据
memset(dist, 0x3f, sizeof dist);
memset(st, 0, sizeof st);
memset(cnt, 0, sizeof cnt);
queue<int> q;
q.push(1);
dist[1] = 0;
st[1] = true;
//cnt[1] = 0;
while (q.size())
{
auto u = q.front(); q.pop();
st[u] = false;
for (auto& e : edges[u])
{
int v = e.first, w = e.second;
if (dist[u] + w < dist[v])
{
dist[v] = dist[u] + w;
dist[v] = dist[u] + 1;
if (dist[v] > n – 1) return true;
if (!st[v])
{
q.push(v);
st[v] = true;
}
}
}
}
return false;
}
int main()
{
int t; cin >> t;
while (t–)
{
// 清空数据
for (int i = 1; i <= n; i++) edges[i].clear();
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
int u, v, w; cin >> u >> v >> w;
edges[u].push_back({ v, w });
if (w >= 0) edges[v].push_back({ u, w });
}
if (spfa()) cout << "YES" << endl;
else cout << "NO" << endl;
}
return 0;
}
