差分约束算法的一些个人理解

update on 2020.4.26 新增糖果代码

浅谈差分约束

差分约束系统 是一种特殊的 $n$ 元一次不等式组,它包含 $n$ 个变量 $x_1,x_2,\cdots x_n$ 以及 $m$ 个约束条件,每个约束条件是由两个其中的变量做差构成的,形如 $x_i-x_j \leq c_k$,其中 $c_k$ 是常数(可以是非负数,也可以是负数)。我们要解决的问题是:求一组解 ,使得所有的约束条件得到满足,否则判断出无解。

差分约束系统中的每个约束条件 $x_i-x_j\leq c_k$ 都可以变形成 $x_i \leq x_j+c_k$,这与单源最短路中的三角形不等式 $dist[y] \leq dist[x]+z$ 非常相似。因此,我们可以把每个变量 $x_i$ 看做图中的一个结点,对于每个约束条件 $x_i-x_j\leq c_k$,从结点 $j$ 向结点 $i$ 连一条长度为 $c_k$ 的有向边。

注意到,如果 ${a_1,a_2,\cdots ,a_n}$ 是该差分约束系统的一组解,那么对于任意的常数 $d$,${a_1+d,a_2+d,\cdots ,a_n}$ 显然也是该差分约束系统的一组解,因为这样做差后 $d$ 刚好被消掉。

设 $dist[0]=0$ 并向每一个点连一条边,跑单源最短路,若图中存在负环,则给定的差分约束系统无解,否则,$x_i=dist[i]$ 为该差分约束系统的一组解。

一般使用 Bellman-Ford 或队列优化的 Bellman-Ford(俗称 SPFA,在某些随机图跑得很快)判断图中是否存在负环,最坏时间复杂度为 $O(nm)$。

个人理解:

  1. 差分约束系统是一种特殊的 $n$ 元一次不等式组

  2. 约束条件形如 $x_i-x_j \leq c_k$

  3. 一些对照

差分约束中的条件 三角形不等式中的条件
$x_i$​ $dist[y]$
$x_j$​ $dist[x]$
$c_k$​ $z$​
  1. $dist[0]$ 其实就是建立了超级源点

  2. 以此为例建图

    显然 1→2→3→1 形成了一个负环,显然是不可解的(此时无最短路)

  3. 为什么?我的理解是如果建出的图存在有负环,那么原差分约束系统中的约束条件必然相互矛盾,上例中是 $x_1 \leq x_1-5$

  4. 实际上这是一种抽象的概念,将某一类复杂的问题巧妙的结合在图论模型中再用最短路求解,实际上,图论问题,建图最难

SPFA虽然已经成为了被卡掉的算法(包括各个优化),其实用性仍然是很好的。

如果以 $x_1,x_2$ 表示两个变量,$x_1-x_2 \leq c$ 有如下条件是等价的

如果 $x_1-x_2=c$,有 $x_1-x_2 \geq c,x_1-x_2 \leq c$

(其实上面的做法是为了解决糖果这道题)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+5,M = N*3;
#define ll long long
int n,m,op,x,y,idx,v[M],w[M],dis[N],book[N],cnt[N],first[N],nxt[M];
ll ans;
void add(int x,int y,int z) {
v[++idx]=y;
w[idx]=z;
nxt[idx]=first[x];
first[x]=idx;
}
bool spfa() {
book[0]=1;
queue<int> q;
q.push(0);
memset(dis,-0x3f,sizeof(dis));
dis[0]=0;
while(!q.empty()) {
int t=q.front();
q.pop();
book[t]=0;
if(cnt[t]++==n-1) return false;
for(int i=first[t];i;i=nxt[i]) {
int p=v[i];
if(dis[p]<dis[t]+w[i]) {
dis[p]=dis[t]+w[i];
if(!book[p]) {
book[p]=1;
q.push(p);
}
}
}
}
return true;
}
int main() {
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++) {
scanf("%d%d%d",&op,&x,&y);
switch(op) {
case 1:
add(x,y,0);add(y,x,0);break;
case 2:
add(x,y,1);break;
case 3:
add(y,x,0);break;
case 4:
add(y,x,1);break;
case 5:
add(x,y,0);break;
}
if(op%2==0&&x==y) return printf("-1"),0;
}
for(int i=n;i>=1;i--) add(0,i,1);
if(!spfa())
return printf("-1"),0;
for(int i=1;i<=n;i++) {
ans+=dis[i];
}
printf("%lld",ans);
return 0;
}
文章作者: answerend42
文章链接: http://answerend42.github.io/2020/04/12/%E5%B7%AE%E5%88%86%E7%BA%A6%E6%9D%9F%E7%AE%97%E6%B3%95%E7%9A%84%E4%B8%80%E4%BA%9B%E4%B8%AA%E4%BA%BA%E7%90%86%E8%A7%A3/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 answerend42的Blog