题解 P5960 【【模板】差分约束算法】
一只书虫仔
2020-07-14 10:10:40
#### Description
给定 $n$ 个数 $t_i$，然后给定 $m$ 个用 $i,j,b$ 描述的不等式关系
$$t_i-t_j\le b$$
#### Solution
差分约束模板，左边的这个 $t_i-t_j$ 就是差分。
我们首先把这个不等式化简一下，成 $t_i\le t_j+b$。
假设 $t_j$ 已知，我们可以推出 $t_i$ 的最大值只可能是 $t_j+b$，最小不限。
那我们再次假设如果 $t_i$ 跟 $t_{j'}$，$t_{j''}$，$t_{j'''}$ 都有关，我们就可以得到三个不等式，即一个不等式组
$$\begin{cases}t_i\le t_{j'}+b\\t_i\le t_{j''}+b\\t_i\le t_{j'''}+b\end{cases}$$
那么 $t_i$ 满足所有不等式下的最大值应该是 $\min\{t_{j'}+b,t_{j''}+b,t_{j'''}+b\}$。
因为要满足所有不等式，所以必须要取最小值来满足所有的不等式。
注意，我们上面提到的 $j$ 都可以模拟成 $i$ 的 **前继**。
那么我们可以再次简化模型。
假设有多个 $t_j$ 是 $t_i$ 的前继，那么我们就可以得到一个递推式。
$$t_i=\min\{t_j+b\}$$
那么我们看一下 SPFA 的递推式。
$$dist_i=\min\{dist_j+<i,j>\}$$
好了，破案了。
那么我们只需要找一个超级原点 $\rm super$，然后使得他连到 $i$ 的长度是 $t_i$ 即可。
最后我们求一个最短路即可，输出每个 $dist_i-\min\{dist_i\}$。
最后无解的情况只需要判断一下负环即可。
#### Code
```cpp
#include <bits/stdc++.h>
using namespace std;
struct node {
int val, next, len;
} e[100086];
int n, m;
int cnt;
int head[100086];
int dist[100086];
int sum[100086];
int vis[100086];
const int inf = 0x3f3f3f3f;
void AddEdge (int u, int v, int w) {
e[++cnt].val = v;
e[cnt].next = head[u];
e[cnt].len = w;
head[u] = cnt;
}
bool SPFA () {
queue <int> q;
int s = n + 1;
for (int i = 1; i <= n; i++)
dist[i] = inf;
dist[s] = 0;
sum[s] = 1;
vis[s]++;
q.push(s);
while (!q.empty()) {
int cur = q.front();
q.pop();
sum[cur] = 0;
for (int p = head[cur]; p > 0; p = e[p].next)
if (dist[e[p].val] > dist[cur] + e[p].len) {
dist[e[p].val] = dist[cur] + e[p].len;
vis[e[p].val]++;
if (vis[e[p].val] >= n + 1)
return true;
if (!sum[e[p].val]) {
q.push(e[p].val);
sum[e[p].val] = 1;
}
}
}
return false;
}
int main () {
scanf("%d%d", &n, &m);
for (int i = 1, u, v, w; i <= m; i++) {
scanf("%d%d%d", &u, &v, &w);
AddEdge(v, u, w);
}
for (int i = 1; i <= n; i++)
AddEdge(n + 1, i, 0);
if (SPFA()) {
printf("NO");
return 0;
}
int Min = 1e9;
for (int i = 1; i <= n; i++)
Min = min(dist[i], Min);
for (int i = 1; i <= n; i++)
printf("%d ", dist[i] - Min);
return 0;
}
```
2020.7.14
By Shuchong