开篇碎碎念
每次都是以开篇碎碎念开头，虽然不知道为什么，但似乎成为了惯例。本来是直接看的差分约束，一上来发现一堆不等式，以为是数学的一个tag乱入图论(x，结果发现还真的是建图来做的，然后学了一下之后...负边权？！跑不了dijkstra啊！！于是学了一下SPFA（虽然...SPFA已死）然后顺道写了一下关于负环的判断
SPFA
- 算法思路： 设立一个先进先出的队列用来保存待优化的结点，优化时每次取出队首结点u，并且用u点当前的最短路径估计值对离开u点所指向的结点v进行松弛操作，如果v点的最短路径估计值有所调整，且v点不在当前的队列中，就将v点放入队尾。这样不断从队列中取出结点来进行松弛操作，直至队列空为止。
- 例题：单源最短路SPFA
- code:
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 5e5 + 10;
const int inf = 2147483647;
int dist[MAXN];
int vis[MAXN];
vector<pair<int, int> >e[MAXN];
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n, m, st;
cin >> n >> m >> st;
for (int i = 1; i <= n; i++) {
dist[i] = inf;
}
dist[st] = 0;
int u, v, w;
for (int i = 1; i <= m; i++) {
cin >> u >> v >> w;
e[u].push_back({v, w});
// cout<<i<<endl;
}
// for(int i=1;i<=n;i++){
// cout<<i<<':'<<endl;
// for(auto j:e[i]){
// cout<<j.first<<' '<<j.second<<endl;
// }
// }
queue<int> q;
q.push(st);
vis[st] = 1;
while (!q.empty()) {
st = q.front();
vis[st]=0;
q.pop();
for (auto i : e[st]) {
v = i.first;
w = i.second;
if (dist[st] + w < dist[v]) {
dist[v] = dist[st] + w;
if (!vis[v]) {
q.push(v);
vis[v] = 1;
}
}
}
}
for (int i = 1; i <= n; i++) {
cout << dist[i] << " \n"[i==n];
}
return 0;
}
负环的判断——基于SPFA
- 什么是负环：负环就是负权回路，就是边权和小于0的环，负环上面没有最短路，因为只要绕圈子走下去那么就会将路径长度减小
- 如何判断是否存在负环：在SPFA中，对于一个点的松弛操作最多执行n-1次，而且他的最短路长度最长为n-1；因此只要增加一个cnt数组记录每个点的松弛次数或者最短路长度
- 例题：负环
- code：
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 2e3 + 10;
const int inf = 2147483647;
int dist[MAXN];
int vis[MAXN];
int cnt[MAXN];
vector<pair<int, int> >e[MAXN];
void sol() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
dist[i] = inf;
vis[i] = 0;
cnt[i] = 0;
e[i].clear();
}
int u, v, w;
for (int i = 1; i <= m; i++) {
cin >> u >> v >> w;
if (w >= 0) {
e[u].push_back({v, w});
e[v].push_back({u, w});
}
else {
e[u].push_back({v, w});
}
}
dist[1] = 0;
vis[1] = 1;
queue<int>q;
q.push(1);
int st;
int f = 0;
while (!q.empty()) {
st = q.front();
vis[st] = 0;
q.pop();
for (auto i : e[st]) {
v = i.first;
w = i.second;
if (dist[st] + w < dist[v]) {
dist[v] = dist[st] + w;
cnt[v] = cnt[st] + 1;
if(cnt[v] >= n){
f=1;
break;
}
if (!vis[v]) {
q.push(v);
vis[v] = 1;
}
}
}
if (f == 1)break;
}
if (f == 1)cout << "YES" << endl;
else cout << "NO" << endl;
}
signed main() {
int t;
cin >> t;
while (t--) {
sol();
}
}
差分约束
- 实质：将 x-y<=z 的式子转化为 x<=y+z 发现与最短路求解的松弛式子相似; 于是将z视为边权，即有一条y指向x 权值为z的有向边。从而建图。
- 技巧：构建一个虚拟的超级原点0，其到所有（非本身）的点边权都为0.防止由不等式组构成的图不连通。
- 例题：差分约束
- code:
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int MAXN = 2e5 + 10;
const int inf = 0x3f3f3f3f;
int vis[MAXN];
int dist[MAXN];
int cnt[MAXN];
vector<pair<int, int> >e[MAXN];
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
dist[i] = inf;
}
int u, v, w;
for (int i = 1; i <= m; i++) {
cin >> v >> u >> w;
e[u].push_back({v, w});
}
for (int i = 1; i <= n; i++) {
e[0].push_back({i, 0});
}
queue<int>q;
q.push(0);
vis[0] = 1;
while (!q.empty()) {
u = q.front();
q.pop();
vis[u] = 0;
for (auto i : e[u]) {
v = i.first;
w = i.second;
if (dist[v] > dist[u] + w) {
dist[v] = dist[u] + w;
if (!vis[v]) {
if (++cnt[v] > n) {
cout << "NO" << endl;
return 0;
}
vis[v] = 1;
q.push(v);
}
}
}
}
for (int i = 1; i <= n; i++) {
cout << dist[i] << " \n"[i == n];
}
return 0;
}