spfa 判断负环

简介: 笔记

SPFA判断负环


基本过程与spfa求最短路相同,但是额外记录一个 cnt数组,表示到当前点的最短路经过的边的条数,如果cnt[i]>=n说明一定存在一个负环。

此外,初始化队列的时候,要将所有点都加入队列,因为1可能到不了负环存在的位置。

#include<bits/stdc++.h>
#include<unordered_map>
// #define int long long
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3f
#define mod 1000000007
#define MOD 998244353
#define rep(i, st, ed) for (int (i) = (st); (i) <= (ed);++(i))
#define pre(i, ed, st) for (int (i) = (ed); (i) >= (st);--(i))
#define debug(x,y) cerr << (x) << " == " << (y) << endl;
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
template<typename T> inline T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template<typename T> inline T lowbit(T x) { return x & -x; }
//template<typename T> T qmi(T a, T b = mod - 2, T p = mod) { T res = 1; b %= (p - 1 == 0 ? p : p - 1); while (b) { if (b & 1) { res = (LL)res * a % p; }b >>= 1; a = (LL)a * a % p; }return res % mod; }
const int N = 1e5 + 10;
int n, m;
vector<PII>vec[N];
int d[N], cnt[N];
bool vis[N];
bool spfa() {
    queue<int>q;
    memset(d, 0x3f, sizeof d);
    d[1] = 0;
    vis[1] = true;
    for (int i = 1; i <= n; ++i)q.push(i);
    while (q.size()) {
        int t = q.front();
        q.pop();
        vis[t] = false;
        for (int i = 0; i < vec[t].size(); ++i) {
            int j = vec[t][i].second;
            int dis = vec[t][i].first;
            if (d[j] > d[t] + dis) {
                d[j] = d[t] + dis;
                if (!vis[j])q.push(j);
                cnt[j] = cnt[t] + 1;
                if (cnt[j] >= n)return true;
            }
        }
    }
    return false;
}
void solve() {
    cin >> n >> m;
    while (m--) {
        int u, v, w; scanf("%d%d%d", &u, &v, &w);
        vec[u].push_back({ w,v });
    }
    if (spfa())puts("Yes");
    else puts("No");
}
signed main() {
    // int _; cin >> _;
    // while (_--)
        solve();
    return 0;
}
目录
相关文章
|
算法
SPFA算法-最短路-负环
SPFA算法-最短路-负环
90 0
|
7月前
|
存储 算法
最短路之SPFA算法
最短路之SPFA算法
58 0
spfa判断负环的应用
spfa判断负环的应用
49 0
spfa处理差分约束
spfa处理差分约束
45 0
poj 1088 记忆化搜索||动态规划
记忆化搜索也也是采用递归深搜的对数据进行搜索,但不同于直接深搜的方式,记忆化搜索是在每次搜索时将得到的结果保存下来,避免了重复计算,这就是所谓的记忆化。记忆化应该是属于动态规划。
41 0
|
算法
BFS——二分图判断
BFS——二分图判断
124 0
BFS——二分图判断
|
存储 算法
spfa算法的实现
spfa算法的实现
|
算法 C++
spfa
复习acwing算法基础课的内容,本篇为讲解基础算法:spfa,关于时间复杂度:目前博主不太会计算,先鸽了,日后一定补上。
124 0
spfa
|
算法
spfa 算法模板
spfa 算法模板
97 0