欢迎访问==> 【考研OR保研】机试题
题目描述
给定一个 $n$ 个点 $m$ 条边的有向图,图中可能存在重边和自环, 边权可能为负数。
请你判断图中是否存在负权回路。
输入格式
第一行包含整数 $n$ 和 $m$。
接下来 $m$ 行每行包含三个整数 $x,y,z$,表示存在一条从点 $x$ 到点 $y$ 的有向边,边长为 $z$。
输出格式
如果图中存在负权回路,则输出 Yes
,否则输出 No
。
数据范围
$1 \\le n \\le 2000$,
$1 \\le m \\le 10000$,
图中涉及边长绝对值均不超过 $10000$。
输入样例:
3 3
1 2 -1
2 3 4
3 1 -4
输出样例:
Yes
C++ 代码
本题基于spfa求最短路算法,具体请参考spfa求最短路
/*
spfa判负环
只需要在spfa求最短路的同时维护一个cnt数组表示经过的边数
当cnt[i] >= n时,说明出现了负环
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 2010, M = 10010;
int n, m, d[N], cnt[N];
int h[N], e[M], nxt[M], w[M], idx;
bool st[N];
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, nxt[idx] = h[a], h[a] = idx ++;
}
bool spfa()
{
queue<int> q;
memset(d, 0x3f, sizeof d);
memset(st, 0, sizeof st);
d[1] = 0;
/*遍历每一个点去更新其他点的情况
因为有可能只让1号点作为起点时,图中的负环可能与1号点是不连通的
所以需要遍历每一个点去更新其他点的情况
*/
for(int i = 1; i <= n; i ++)
{
q.push(i);
st[i] = true;
}
while(q.size())
{
int t = q.front();
q.pop(), st[t] = false;
for(int i = h[t]; i != -1; i = nxt[i])
{
int j = e[i];
if(d[j] > d[t] + w[i])
{
d[j] = d[t] + w[i];
cnt[j] = cnt[t] + 1; //更新cnt数组
if(cnt[j] >= n) return true;
if(!st[j]) q.push(j), st[j] = true;
}
}
}
return false;
}
int main()
{
memset(h, -1, sizeof h);
cin >> n >> m;
while(m -- )
{
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
}
if(spfa()) puts("Yes");
else puts("No");
return 0;
}