【Bellman负环】Cycle Finding
题目翻译
给定一个有向图，你的任务是判断它是否包含负环，并给出这样一个环的示例。
输入
第一行输入两个整数 n 和 m：分别表示节点数和边数。节点编号为 1, 2, ..., n。
接下来 m 行描述边，每行有三个整数 a, b, c：表示存在一条从节点 a 到节点 b 的边，长度为 c。图中可能存在自环。约束条件
- 1 ≤ n ≤ 2500
- 1 ≤ m ≤ 5000
- 1 ≤ a, b ≤ n
- -10⁹ ≤ c ≤ 10⁹
输出
如果图包含负环，先输出 "YES"，然后按正确顺序输出环中的节点。如果存在多个负环，输出任意一个即可。如果没有负环，输出 "NO"。样例输入
复制
4 5 1 2 1 2 4 1 3 1 1 4 1 -3 4 3 -2样例输出
复制
YES 1 2 4 1
1. dis 初始化为0（寻找负环）
2. 寻找路径
Bellman-Ford 算法检测负环的逻辑是：若第 n 次松弛（即对所有边再做一次松弛操作）仍能更新某个节点的距离，则说明存在负环。
这里被更新的节点res可能有两种情况：
res本身就在负环上；res不在负环上，但存在一条从负环指向res的路径（即负环的 “下游”）。因为负环可以无限降低路径权重，所以res的距离能被不断更新。
由于负环的长度最多为
n，回溯n次后，p必然会落入负环内部（无论res最初是否在负环上）。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;int n,m;int main()
{cin>>n>>m;vector<tuple<int,int,int>>adj;for(int i=0;i<m;++i){int a,b,c;cin>>a>>b>>c;adj.emplace_back(a,b,c);}vector<ll>dis(n+1,0);vector<int>pre(n+1,-1);int res=-1;for(int i=0;i<n;++i){res=-1;for(auto [a,b,c]:adj){if(dis[a]+c<dis[b]){dis[b]=dis[a]+c;pre[b]=a;res=b;}}}if(res==-1){cout<<"NO";return 0;}cout<<"YES\n";int p=res;for(int i=0;i<n;++i){p=pre[p];}int start=p;p=pre[p];vector<int>path;path.push_back(start);while(p!=start){path.push_back(p);p=pre[p];}path.push_back(start);reverse(path.begin(),path.end());for(auto i:path)cout<<i<<" ";return 0;
}