洛谷t341352负环判断
时间: 2023-08-20 15:39:05 浏览: 114
判断负环的经典算法是 Bellman-Ford 算法。该算法的主要思想是进行 n 次松弛操作,其中 n 为图中节点的数量。如果在第 n 次松弛操作后仍然存在可以被松弛的边,则说明图中存在负环。
在具体实现时,可以先将所有节点的距离初始化为正无穷大,起始节点的距离为 0。然后进行 n 次松弛操作,每次松弛操作都枚举所有边,如果该边的起点的距离加上边的权值小于终点的距离,则更新终点的距离。如果在第 n 次松弛操作后仍然存在可以被松弛的边,则说明图中存在负环。
具体代码实现可以参考以下代码:
```cpp
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
const int INF = 0x3f3f3f3f;
struct Edge {
int to, weight;
Edge(int _to, int _weight) : to(_to), weight(_weight) {}
};
vector<Edge> edges[1000];
int dist[1000];
bool inQueue[1000];
bool bellmanFord(int start, int n) {
memset(dist, INF, sizeof(dist));
dist[start] = 0;
queue<int> q;
for (int i = 1; i <= n; i++) {
q.push(i);
inQueue[i] = true;
}
while (!q.empty()) {
int u = q.front();
q.pop();
inQueue[u] = false;
for (int i = 0; i < edges[u].size(); i++) {
int v = edges[u][i].to;
int w = edges[u][i].weight;
if (dist[u] != INF && dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
if (!inQueue[v]) {
q.push(v);
inQueue[v] = true;
}
if (dist[v] < 0) {
return true;
}
}
}
}
return false;
}
int main() {
int n, m;
cin >> n >> m;
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
edges[u].push_back(Edge(v, w));
}
if (bellmanFord(1, n)) {
cout << "YES" << endl;
} else {
cout << "NO" << endl;
}
return 0;
}
```