uva 558 - Wormholes(Bellman Ford判断负环)
判断 UVa
2023-09-11 14:20:13 时间
题目大意:给出n和m,表示有n个点,然后给出m条边,然后判断给出的有向图中是否存在负环。
解题思路:利用Bellman Ford算法,若进行第n次松弛时,还能更新点的权值,则说明有负环的存在。
#include <stdio.h> #include <string.h> #define min(a,b) (a)<(b)?(a):(b) const int N = 10005; const int INF = 0x3f3f3f3f; int n, m, flag, d[N]; int x[N], y[N], v[N]; void init() { scanf("%d%d", &n, &m); for (int i = 0; i < m; i++) scanf("%d%d%d", &x[i], &y[i], &v[i]); } void BF() { flag = 0; for (int i = 0; i < n; i++) d[i] = INF; d[0] = 0; for (int k = 1; k < n; k++) { for (int i = 0; i < m; i++) { int a = x[i], b = y[i]; if (d[a] < INF) d[b] = min(d[a] + v[i], d[b]); } } for (int i = 0; i < m; i++) { int a = x[i], b = y[i]; if (d[b] > d[a] + v[i]) { flag = 1; return; } } } int main () { int cas; scanf("%d", &cas); while (cas--) { init(); BF(); printf("%s\n", flag ? "possible" : "not possible"); } return 0; }
相关文章
- java中判断一个字符在字符串中出现的次数
- 判断一个男人穷还是富,只看这几点!
- uni-app:微信小程序:使用位置前先判断是否有权限授权(hbuilderx 3.7.3)
- 哪些操作需要判断账号是否存在
- mysql--SQL编程(关于mysql中的日期,实例,判断生日是否为闰年) 学习笔记2.1
- 判断当前的Activity的是否处于栈顶
- Android 根据file路径判断文件类型
- Python每日一练——第14天:蓝桥真题判断美国数学家维纳年龄
- [算法]快速判断一个数是否是2的幂次方
- 【数字信号处理】周期序列 ( 周期序列示例 3 | 判断序列是否是周期序列 )
- python基础===isinstance() 函数,判断一个对象是否是一个已知的类型
- JS判断包含:includes