【题目来源】
洛谷：P3385 【模板】负环 - 洛谷
【题目描述】
给定一个 \(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
【算法标签】
《洛谷 P3385 负环》 #模板题# #O2优化#
【代码详解】
//Ford 判负环 740ms
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cstring> // 需要包含memset
using namespace std;const int inf = 0x3f3f3f3f; // 定义无穷大
const int N = 2010; // 最大顶点数
const int M = 6010; // 最大边数
int n, m; // 顶点数，边数
int to[M], ne[M], w[M], h[N], tot; // 链式前向星
int d[N]; // 最短距离数组/*** 添加有向边* @param a 起点* @param b 终点* @param c 权重*/
void add(int a, int b, int c)
{to[++tot] = b; // 边指向的顶点w[tot] = c; // 边的权重ne[tot] = h[a]; // 指向原链表头h[a] = tot; // 更新头指针
}/*** Bellman-Ford算法实现，检测负权环* 原理：如果没有负权环，最多n-1轮松弛可得到最短路径* 如果第n轮还能松弛，说明存在负权环* @return 存在负权环返回true，否则返回false*/
bool ford()
{memset(d, inf, sizeof d); // 初始化距离为无穷大d[1] = 0; // 假设起点为1，距离为0bool flag; // 标记本轮是否进行了松弛操作// 最多进行n轮松弛for (int i = 1; i <= n; i++) // 跑n轮{flag = false; // 初始化为未松弛// 遍历所有顶点for (int u = 1; u <= n; u++) // n个点{if (d[u] == inf) // 如果当前顶点不可达，跳过{continue;}// 遍历u的所有出边for (int j = h[u]; j; j = ne[j]){int v = to[j]; // 邻接顶点// 松弛操作if (d[v] > d[u] + w[j]){d[v] = d[u] + w[j];flag = true; // 标记有松弛}}}// 如果本轮没有松弛，提前结束if (!flag){break;}}// 如果第n轮还能松弛，说明存在负权环return flag; // 第n轮=true,有负环
}int main()
{int T; // 测试用例数量scanf("%d", &T);while (T--){// 初始化邻接表tot = 0;memset(h, 0, sizeof(h));// 输入顶点数和边数scanf("%d%d", &n, &m);// 读入边for (int i = 1; i <= m; i++){int u, v, w;scanf("%d%d%d", &u, &v, &w);add(u, v, w); // 添加有向边// 如果是非负边，添加反向边（构成无向边）if (w >= 0){add(v, u, w);}}// 检测负权环并输出结果puts(ford() ? "YES" : "NO");}return 0;
}
// 使用acwing模板二刷
#include <bits/stdc++.h>
using namespace std;const int N = 2005; // 最大顶点数
const int M = 6005; // 最大边数int h[N], e[M], w[M], ne[M], idx; // 链式前向星存储图
int dist[N]; // 最短距离数组
int cnt[N]; // 记录每个顶点被松弛的次数
bool st[N]; // 标记顶点是否在队列中
int T, n, m; // T: 测试用例数, n: 顶点数, m: 边数/*** 添加有向边* @param a 起点* @param b 终点* @param c 权重*/
void add(int a, int b, int c)
{e[idx] = b; // 边指向的顶点w[idx] = c; // 边的权重ne[idx] = h[a]; // 指向原链表头h[a] = idx++; // 更新头指针
}/*** SPFA算法检测负权环* 从所有顶点开始检测，确保能找到任意连通分量中的负权环* @return 存在负权环返回true，否则返回false*/
int spfa()
{queue<int> q;// 初始化memset(dist, 0, sizeof(dist)); // 距离初始化为0memset(cnt, 0, sizeof(cnt)); // 松弛次数初始化为0// 将所有顶点入队for (int i = 1; i <= n; i++){st[i] = true; // 标记在队列中q.push(i); // 顶点入队}// SPFA主循环while (q.size()){int t = q.front(); // 取出队首顶点q.pop();st[t] = false; // 标记不在队列中// 遍历t的所有邻接边for (int i = h[t]; i != -1; i = ne[i]){int j = e[i]; // 邻接顶点// 松弛操作if (dist[j] > dist[t] + w[i]){dist[j] = dist[t] + w[i]; // 更新最短距离cnt[j] = cnt[t] + 1; // 松弛次数+1// 如果顶点j被松弛了n次，说明存在负权环if (cnt[j] >= n){return true; // 存在负权环}// 如果j不在队列中，入队if (!st[j]){q.push(j);st[j] = true;}}}}return false; // 不存在负权环
}int main()
{// 输入测试用例数量cin >> T;while (T--){// 输入顶点数和边数cin >> n >> m;// 初始化邻接表memset(h, -1, sizeof(h));idx = 0; // 重置边索引// 读入边for (int i = 1; i <= m; i++){int a, b, c;cin >> a >> b >> c;add(a, b, c); // 添加有向边// 如果是非负边，添加反向边（构成无向边）if (c >= 0){add(b, a, c);}}/*** 判断是否存在从顶点1出发可达的负权环* 条件：* 1. 存在负权环 (!spfa() 返回false时表示有负环)* 2. 顶点1必须有出边 (h[1] != -1)* 注意：spfa()返回true表示有负环，false表示无负环* 但题目要求"从1出发不存在负环"时输出"NO"* 这里条件为：!spfa() || h[1] == -1* 即：无负环 或 顶点1无出边*/if (!spfa() || h[1] == -1) // 注意：spfa()返回true表示有负环{cout << "NO" << endl; // 题目要求是从1出发不存在负环}else{cout << "YES" << endl;}}return 0;
}
【运行结果】
2
3 4
1 2 2
1 3 4
2 3 1
3 1 -3
NO
3 3
1 2 3
2 3 4
3 1 -8
YES