差分约束 笔记
给定约束 \(n\) 个未知数的 \(m\) 个约束条件，求满足条件的未知数的其中一个整数解。
\(m\) 个约束条件如下：
\[\left \{ \begin{matrix} x_{c_1} + w_1 \ge x_{c'_1}\\ x_{c_2} + w_2 \ge x_{c'_2}\\ x_{c_3} + w_3 \ge x_{c'_3}\\ \dots \\ x_{c_m} + w_m \ge x_{c'_m} \end{matrix} \right. \]通俗的讲，将 \(u = c_i, v = c'_i\)，\(x_u + w \ge x_v\)，而 \(x_u\) 表示第 \(u\) 个未知数，放在 \(a\) 数组里表示 \(a_u\)。
于是，式子变形成：
\[a_u + w \ge a_v \]换个变量名，\(a \to dis\)：
\[dis_u + w \ge dis_v \]想到了三角不等式，最短路的松弛操作，于是我们可以将这个式子理解成 \(u \to v\) 有一条权值为 \(w\) 的有向边。
于是可以建图。
例如下面不等式：
\[\left \{ \begin{matrix} dis_2 + 3 \ge dis_1 \\ dis_3 + (-2) \ge dis_2 \\ dis_3 + 1 \ge dis_1 \\ \end{matrix} \right. \]可以建图为：并跑最短路，\(dis\) 数组即为答案。
当然，原式也可以转换成：
\[x_i - w \le x_i' \]也就是说，我们可以反向建边并跑最长路。观察出最长路的 \(dis\) 数组会比最短路的 \(dis\) 数组要小，所以用最短路跑出来的是大解，用最长路跑出来的是小解。
无解情况即有负环。
所以跑一边 SPFA 即可。
注意，在建图中，可以用一个编号为 \(0\) 的超级源点连接所有点，边权为 \(0\)。
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
using ll = long long;
const int N = 5e3 + 5;
struct edge{
int v, w;
};
int n, m, dis[N], vis[N], cnt[N];
vector<edge> g[N];
bool spfa() {
memset(dis, 0x3f, sizeof dis);
dis[0] = 0, vis[0] = 1;
queue<int> q;
q.push(0);
while (!q.empty()) {
int u = q.front();
q.pop();
vis[u] = 0;
for (auto x : g[u]) {
int v = x.v, w = x.w;
if (dis[u] + w < dis[v]) {
dis[v] = dis[u] + w;
cnt[v] = cnt[u] + 1;
if (cnt[v] > n) return false;
if (vis[v]) continue;
vis[v] = 1;
q.push(v);
}
}
}
return true;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int u, v, w;
cin >> u >> v >> w;
g[v].pb({u, w});
}
for (int i = 1; i <= n; i++) g[0].pb({i, 0});
if (!spfa()) cout<<"NO";
else {
for (int i = 1; i <= n; i++) cout << dis[i] << " ";
}
return 0;
}