AcWing 852. spfa判断负环
\(AcWing\) \(852\). \(spfa\)判断负环
一、题目描述
给定一个 \(n\) 个点 \(m\) 条边的有向图,图中可能存在重边和自环, 边权可能为负数。
请你判断图中是否存在负权回路。
输入格式
第一行包含整数 \(n\) 和 \(m\)。
接下来 \(m\) 行每行包含三个整数 \(x,y,z\),表示存在一条从点 \(x\) 到点 \(y\) 的有向边,边长为 \(z\)。
输出格式
如果图中存在负权回路,则输出 Yes
,否则输出 No
。
数据范围
\(1≤n≤2000,1≤m≤10000\),
图中涉及边长绝对值均不超过 \(10000\)。
输入样例:
3 3
1 2 -1
2 3 4
3 1 -4
输出样例:
Yes
二、解题思路
-
\(spfa\)可以用来判断是不是有向图中存在负环。
-
基本原理:利用 抽屉原理
\(dist[x]\)的概念是指当前从虚拟源点到\(x\)号点的最短路径的长度。\(dist[x]=dist[t]+w[i]\)
\(cnt[x]\)的概念是指当前从虚拟源点到\(x\)号点的最短路径的边数量。\(cnt[x]=cnt[t]+1\)
如果发现\(cnt[x]>=n\),就意味着从虚拟源点\(\sim x\)经历了\(n\)条边,那么必须经过了\(n+1\)个点,但问题是点一共只有\(n\)个,所以必然有两个点是相同的,就是有一个环。
因为是在不断求最短路径的过程中发现了环,路径长度在不断变小的情况下发现了环,那么,只能是负环。 -
为什么初始化时初始值为\(0\),而且把所有结点都加入队列?
在原图的基础上新建一个虚拟源点,从该点向其他所有点连一条权值为\(0\)的有向边。那么原图有负环等价于新图有负环。此时在新图上做\(spfa\),将虚拟源点加入队列中。然后进行\(spfa\)的第一次迭代,这时会将所有点的距离更新并将所有点插入队列中。执行到这一步,就等价于下面代码中的做法了。如果新图有负环,等价于原图有负环。
三、实现代码
#include <bits/stdc++.h>
using namespace std;
const int N = 2010, M = 10010;
int n, m; // 点数、边数
int d[N]; // 存储每个点到1号点的最短距离
bool st[N]; // 存储每个点是否在队列中
int cnt[N]; //
// 邻接表
int e[M], h[N], idx, w[M], ne[M];
void add(int a, int b, int c) {
e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}
int spfa() {
queue<int> q;
// 构建超级源点,防止负环与出发点不连通
for (int i = 1; i <= n; i++) {
q.push(i);
st[i] = true;
}
while (q.size()) {
int u = q.front();
q.pop();
st[u] = 0;
for (int i = h[u]; ~i; i = ne[i]) {
int v = e[i];
if (d[v] > d[u] + w[i]) {
d[v] = d[u] + w[i];
cnt[v] = cnt[u] + 1;
if (cnt[v] >= n) return 1;
if (!st[v]) {
q.push(v);
st[v] = 1;
}
}
}
}
return 0;
}
int main() {
memset(h, -1, sizeof h);
cin >> n >> m;
while (m--) {
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
}
// 调用spfa判断是否有负环
if (spfa())
puts("Yes");
else
puts("No");
return 0;
}
相关文章
- hdu1269迷宫城堡(判断有向图是否是一个强连通图)
- 新零售空间数据库实践一例 - PostGIS 点面叠加视觉判断输出
- java判断字符串是否包含汉字工具类
- 如何判断一个字符串是否是UTF8编码
- Java 常用工具类---- 各种字符集编码判断与转换
- shell命令操作(jenkins执行后判断shell执行的对与错)
- mybatis 关于 if test 判断字符串的大坑
- 《不确定世界中的理性选择:判断与决策心理学》笔记
- AcWing 2816. 判断子序列
- 给定两个字符串 s 和 t ,编写一个函数来判断 t 是否是 s 的一个字母异位词。
- jQuery 复选框设置选中、取消选中、获取被选中的值、判断是否被选中
- 【jvm我能讲两小时038】 jvm是如何判断对象是否存活的?
- 【集合我能讲两小时009】jdk1.8的hashmap为什么在链表长度为8的时候判断红黑树?