【差分约束】学习笔记
xAlec
·
·
算法·理论
Basic Tips
差分约束，即为存在一个差分约束系统，即类似 x_i - x_j \leq k 的 n 元一次不等式组，求出一组解使得该组内所有不等式全部成立，即 x_1 = s_1,x_2 = s_2 \dots x_n = s_n，否则判无解。
对于满足条件的一个解集 \{s_1,s_2,s_3,\dots,s_n\}，集合 \{s_1 + t,s_2 + t,s_3 + t,\dots,s_n + t\} 也满足成为解集的条件。
为何用 spfa 求解？
名副其实，对于每一个不等式 x_i - x_j \leq k，移项可得 x_i \leq x_j + k，与 \text{spfa} 中的三角不等式极其相似，因此可以看做是 x_j 向 x_i 连了一条边权为 k 的有向边，然后就可以用 \text{spfa} 求解，若过程中存在负环则差分约束系统无解，否则对于 s_i = dis_i 即为差分约束系统的一个解。
注：\text{spfa} 跑最长路还是最短路的情况依据推出的差分约束系统不等式的形式，若为 x_i - x_j \leq k，我们选择最短路，若 x_i - x_j \geq k，我们选择最长路。
other
如图：
$v$ 为终点，$u$ 为起点，$v1$ 为中转点，显然，$u \to v1 \to v$ 的路径是比 $u \to v$ 的路径长的，因此 $\text{spfa}$ 的过程可以看成对于每个点的出边做一次这样的操作。
## example
[P5960 【模板】差分约束](https://www.luogu.com.cn/problem/P5960)
差分约束模板，根据上文所说的过程实现就行，需要注意的是，在没有保证建出的图联通时，需要从超级源点向每一条点连边。
### code
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 5e3 + 10;
int n,m,idx=1,head[MAXN << 1];
int dist[MAXN << 1],cnt[MAXN << 1];
bool vis[MAXN << 1];
struct node{
int v,w,nxt;
}edge[MAXN << 1];
inline void add(int u,int v,int w){
edge[idx].v = v;
edge[idx].w = w;
edge[idx].nxt = head[u];
head[u] = idx ++;
}
inline bool spfa(int s){
memset(cnt,0,sizeof cnt);
memset(dist,-0x3f,sizeof dist);
memset(vis,0,sizeof vis);
queue<int>q;
vis[s] = 1;
dist[s] = 0;
q.push(s);
while(!q.empty()){
int u = q.front();
q.pop();
vis[u] = 0;
for(int i=head[u];i!=-1;i=edge[i].nxt){
int v = edge[i].v,w = edge[i].w;
if(dist[v] < dist[u] + w){
dist[v] = dist[u] + w;
if(!vis[v]){
cnt[v] = cnt[u] + 1;
if(cnt[v] > n + 1)
return false;
vis[v] = 1;
q.push(v);
}
}
}
}
return true;
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
memset(head,-1,sizeof head);
for(int i=1;i<=m;i++){
int u,v,w;
cin >> u >> v >> w;
add(u,v,-w);
}
for(int i=1;i<=n;i++)
add(0,i,0);
if(!spfa(0))
cout << "NO" << endl;
else{
for(int i=1;i<=n;i++)
cout << dist[i] << " ";
cout << endl;
}
return 0;
}
```
[P4878 [USACO05DEC] Layout G](https://www.luogu.com.cn/problem/P4878)
依据题目中给出的条件列出不等式 。
\begin{cases}
x_i - x_j \leq d1 \ x_k - x_p \geq d2
\end{cases}
然后建边，由于全图不保证联通，因此需要超级源点，从超级源点跑一次 $\text{spfa}$ 判无解，另外从 $1$ 号节点跑统计答案，由于题目中默认条件 $x_i < x_j(i > j)$，需要将相邻两点连边。
### code
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 5e4 + 10;
const int inf = 1e9;
int n,m1,m2,idx = 1,head[MAXN],dis[MAXN],cnt[MAXN];
bool vis[MAXN];
struct node{
int v,nxt,w;
}edge[MAXN];
inline void add(int u,int v,int w){
edge[idx].v = v;
edge[idx].w = w;
edge[idx].nxt = head[u];
head[u] = idx ++;
}
inline int spfa(int s){
memset(dis,0x3f,sizeof(dis));
memset(vis,0,sizeof(vis));
memset(cnt,0,sizeof(cnt));
queue<int>q;
dis[s] = 0;
vis[s] = 1;
q.push(s);
while(!q.empty()){
int u = q.front();
q.pop();
vis[u] = 0;
cnt[u] ++;
if(cnt[u] > n)
return -1;
for(int i = head[u];i != -1;i = edge[i].nxt){
int v = edge[i].v,w = edge[i].w;
if(dis[v] > dis[u] + w){
dis[v] = dis[u] + w;
if(!vis[v]){
vis[v] = 1;
q.push(v);
}
}
}
}
if(dis[n] > inf)
return -2;
return dis[n];
}
signed main(){
memset(head,-1,sizeof(head));
scanf("%lld %lld %lld",&n,&m1,&m2);
for(int i = 1;i <= m1;i ++){
int u,v,w;
scanf("%lld %lld %lld",&u,&v,&w);
add(u,v,w);
}
for(int i = 1;i <= m2;i ++){
int u,v,w;
scanf("%lld %lld %lld",&u,&v,&w);
add(v,u,-w);
}
for(int i = 1;i <= n;i ++) add(0,i,0);
for(int i = 1;i < n;i ++) add(i + 1,i,0);
int tmp = spfa(0);
if(tmp <= -1)
printf("%lld\n",tmp);
else
printf("%lld\n",spfa(1));
return 0;
}
```
## 习题
[P1993 小 K 的农场](https://www.luogu.com.cn/problem/P1993)
[P4926 [1007] 倍杀测量者](https://www.luogu.com.cn/problem/P4926) 利用对数的性质转化成差分约束系统
[P2474 [SCOI2008] 天平](https://www.luogu.com.cn/problem/P2474)
[P3530 [POI2012] FES-Festival](https://www.luogu.com.cn/problem/P3530) Tarjan 结合差分约束
[[ABC087D] People on a Line](https://www.luogu.com.cn/problem/AT_arc090_b)