【Luogu】每日一题——Day1. P3385 【模板】负环

链接：P3385 【模板】负环 - 洛谷

题目：

思路：

考察 Bellman-Ford 或 SPFA

本题是一个板子题，也是学到了 Bellman-Ford 和 SPFA

Bellman-Ford 算法的主要思想其实类似迪杰斯特拉，我们暴力枚举每一个点的每一条边，如果能更新最小距离，那么就替换，同时标记该次我们进行了松弛操作，通常情况下 n-1 次松弛操作后我们就能找到最短路了，但是由于可能存在负环，因此我们要注意多判断一次

负环顾名思义就是权值为负的环，既然它为负，那么我们就可以走无数次使得这个环的权值无限小

SPFA 则是利用队列进行了优化，也类似迪杰斯特拉的队列优化，这次我们不再暴力枚举每个点，而是枚举队列中可能更新的点，那么什么情况下可能更新呢？显然是上次更新过的点下次才可能继续更新，因此我们就要提供三个新东西，一个是判断该点是否已经在队列中，一个是判断该点入队了几次，还一个就是队列了

下面提供两个算法的代码

代码：

#include <iostream>
#include <algorithm>
#include<cstring>
#include <iomanip>
#include<cctype>
#include<string>
#include <set>
#include <vector>
#include <cmath>
#include <queue>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <stack>
#include <utility>
#include <array>
#include <tuple>
using namespace std;
#define int long long
#define yes cout << "YES" << endl
#define no cout << "NO" << endlvoid solve()
{int n, m;cin >> n >> m;vector<vector<pair<int,int>>> g(n + 1);for (int i = 0; i < m; i++){int u, v, w;cin >> u >> v >> w;if (w >= 0){g[u].push_back({ v,w });g[v].push_back({ u,w });}else{g[u].push_back({ v,w });}}int flag = 0;vector<int> dis(n + 1, 1e18);dis[1] = 0;for (int i = 1; i <= n; i++){flag = 0;for (int i = 1; i <= n; i++){if (dis[i] == 1e18) continue;for (auto &son : g[i]){if (dis[son.first] > dis[i] + son.second){dis[son.first] = dis[i] + son.second;flag = 1;}}}}flag ? yes : no;
}
signed main()
{//cin.tie(0)->sync_with_stdio(false);int t = 1;cin >> t;while (t--){solve();}return 0;
}

#include <iostream>
#include <algorithm>
#include<cstring>
#include <iomanip>
#include<cctype>
#include<string>
#include <set>
#include <vector>
#include <cmath>
#include <queue>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <stack>
#include <utility>
#include <array>
#include <tuple>
using namespace std;
#define int long long
#define yes cout << "YES" << endl
#define no cout << "NO" << endlvoid solve()
{int n, m;cin >> n >> m;vector<vector<pair<int,int>>> g(n + 1);for (int i = 0; i < m; i++){int u, v, w;cin >> u >> v >> w;if (w >= 0){g[u].push_back({ v,w });g[v].push_back({ u,w });}else{g[u].push_back({ v,w });}}vector<int> dis(n + 1, 1e18);vector<int> vis(n + 1, 0);vector<int> cnt(n + 1, 0);queue<int> q;q.push(1);dis[1] = 0;vis[1] = 1;while (!q.empty()){auto t = q.front();q.pop();vis[t] = 0;for (auto son : g[t]){if (dis[son.first] > dis[t] + son.second){dis[son.first] = dis[t] + son.second;cnt[son.first] = cnt[t] + 1;if (cnt[son.first] >= n){yes;return;}if (!vis[son.first])q.push(son.first), vis[son.first] = 1;}}}no;
}
signed main()
{//cin.tie(0)->sync_with_stdio(false);int t = 1;cin >> t;while (t--){solve();}return 0;
}