B - 负环

题目描述

给定一个 n 个点的有向图，请求出图中是否存在从顶点 11 出发能到达的负环。

负环的定义是：一条边权之和为负数的回路。

输入格式

本题单测试点有多组测试数据。

输入的第一行是一个整数 T，表示测试数据的组数。对于每组数据的格式如下：

第一行有两个整数，分别表示图的点数 n 和接下来给出边信息的条数 m。

接下来 m 行，每行三个整数 u,v,w。

• 若 w≥0，则表示存在一条从 u 至 v 边权为 w 的边，还存在一条从 v 至 u 边权为 w 的边。
• 若 w<0，则只表示存在一条从 u 至 v 边权为 w 的边。

输出格式

对于每组数据，输出一行一个字符串，若所求负环存在，则输出 YES，否则输出 NO。

输入输出样例

输入 #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×10^3，1≤m≤3×10^3。
• 1≤u,v≤n，−10^4≤w≤10^4。
• 1≤T≤10。

提示

请注意，m 不是图的边数。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int N = 1000010;
const int INF = 0x3f3f3f3f;int n, m;
int h[N], w[N], ne[N], e[N], idx;
/*
用邻接表存储图的信息：
h[N]存储所有的表头
e[N]存储所有的边，表示边的终点
w[N]表示边的权重
ne[N]存储每个节点下一个值为多少
idx表示坐标
*/
int dist[N], cnt[N];
//dist[N]表示到某点的最短距离
//cnt[N]表示到某点的组成最短距离所用到的边数bool st[N];
//用于标记当前的点是否在队列中//加入边
void add(int a, int b, int c)
{e[idx] = b; w[idx] = c; ne[idx] = h[a]; h[a] = idx++;
}bool spfa()
{//初始化memset(dist, INF, sizeof dist);memset(st, false, sizeof st);memset(cnt, 0, sizeof cnt);//根据题目所得出的操作：从顶点1出发所能到达的负环queue<int> q;dist[1] = 0;q.push(1);st[1] = true;//直到队内没有元素为止while (q.size()){int temp = q.front(); //取出队首元素q.pop();st[temp] = false;for (int i = h[temp]; i != -1; i = ne[i]){int j = e[i];                  //当前边的终点if (dist[j] > dist[temp] + w[i]) // 如果通过当前节点可以松弛到终点j{dist[j] = dist[temp] + w[i];cnt[j] = cnt[temp] + 1;if (cnt[j] >= n) return true; //若边数为n，则证明有n+1个点，这就是一个负环if (!st[j]){q.push(j);            // 将更新的节点加入队列st[j] = true;}}}}return false;
}int main()
{int t;cin >> t;while (t--){idx = 0;cin >> n >> m;memset(h, -1, sizeof h);for (int i = 0; i < m; i++){int num1, num2, num3;cin >> num1 >> num2 >> num3;if (num3 >= 0){add(num1, num2, num3);add(num2, num1, num3);}else add(num1, num2, num3);}if (spfa()) cout << "YES" << endl;else cout << "NO" << endl;}
}