差分约束系统

给定若干组形如$x_i - x_j \leqslant k_a$($k$为常数)的不等式,询问该不等式组的一组解。
解是指一组$x$,使得$x_1,x_2,…x_n$均满足上述不等式组的限制……

一 基本概念

1 什么是差分约束系统

给定若干组形如$x_i - x_j \leqslant k_a$($k$为常数)的不等式,询问该不等式组的一组解。
解是指一组$x$,使得$x_1,x_2,…x_n$均满足上述不等式组的限制。

2 求解

将不等式变形可得$x_i \leqslant k_a+x_j$。这个限制类似于单源最短路径中总存在$d_i \leqslant dist(j,i)+d_j | (j,i) \in E$。于是我们从$j$向$i$建立一条权为$k_a$的有向边。
再将每个节点与一个源点相连,将这些从源点出发的边的边权定义为一个固定的常数$c$,求出单源最短路,则$x_1=d_1,x_2=d_2,…,x_n=d_n$就是差分约束系统的一组解。当常数$c$改变时,得到的解也会相应地变化(若常数$c$加上$y$,则所有的$d$值均加上$y$,对满足不等关系无影响)。

对上面的不等式,建图得到下图,$s$为源点。
1.1


二 实现

差分约束系统是可能无解的。在求解之前,首先要讨论解的存在性。

1 有解与无解(图上的环)

在一个图上,环的有无及性质决定了差分约束系统解的有无。

环可以分为以下三种:

  1. 正权环:一个正权环在最短路中至多被经过一次。因为当绕这个环第二圈时,只会让走过的路径增大,并且这种增大总是无意义的。
  2. 零权环:相似于正权环,零权环至多被经过一次。因为它并不能使最短路改变。
  3. 负权环:对于一个包含负权环的图,不存在最短路。因为只要在负环中无限转圈,就可以让路径无限变短。

因此任意一个节点最多被$n-1$个节点松弛。
则存在负权环时,一个环上的节点会被松弛无限次,则当任意一个点的松弛次数达到$n$时,不存在最短路,同样不存在差分约束系统的解。

我们只需要记录节点被松弛的次数,即可求出是否有解。

2 SPFA求解差分约束

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
const int CP=1e3+3;
const int CE=CP*404;

const int INF=0x3f3f3f2f;

//边表
class fs{
public:
int to,nxt,dist;
}E[CE];
int hd[CP],ecnt=0;
void add(int x,int y,int z){
E[++ecnt].to=y;
E[ecnt].nxt=hd[x];
E[ecnt].dist=z;
hd[x]=ecnt;
}

//spfa
bool ins[CP]; //是否在队列中
int times[CP]; //times[i] : 节点i被松弛的次数

int d[CP]; //保存单源最短路

bool spfa(int s) //返回有解(true)或无解(false)
{
memset(d,0x3f,sizeof(d));
memset(ins,false,sizeof(ins));
memset(times,0,sizeof(times));

queue<int>Q;
Q.push(s);
d[s]=0;

while(!Q.empty())
{
int u=Q.front();
Q.pop();
ins[u]=false;

for(int k=hd[u]; k; k=E[k].nxt)
{
fs e=E[k];
if(d[u]+e.dist < d[e.to]) //松弛
{
d[e.to]=d[u]+e.dist;
if(!ins[e.to]) //不在队列中就入队
{
Q.push(e.to);
ins[e.to]=true;
if(++times[e.to] == n) //松弛了超过n次,存在负环
return false;
}
}
}
}

return true;
}

3 dfs判断解的存在性

相对于上文算法,这里的dfs算法具有一定激进性。它的复杂度是极不稳定的,在某些保证有解并需要求解的题目中,它比上文算法更好卡掉。
这种方法的主要思路就是记录有哪些元素在当前路径(也就是dfs栈)中。若当松弛操作时,发现正在使用在栈内的元素松弛当前节点(也就是dfs路径绕了一个圈),此时可以直接判定存在负环,不需要松弛$n$次才可以判定。

这种思想有点暴力的意味,因此复杂度不稳定,在某些数据中可能跑的比某某记者还快。
给出核心代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
const int INF=0x3f3f3f3f;

bool ins[CP]; //判断是否在当前路径中
int d[CP]; //最短路数组,需要初始化为INF

bool spfa(int u)
{
ins[u]=true;
for(int k=hd[u]; k; k=E[k].nxt)
{
fs e=E[k];
if(d[e.to] > d[u]+e.dist)
{
d[e.to]=d[u]+e.dist;
if(ins[e.to] || !spfa(e.to)) //又绕回到栈内元素,即出现负环
return false;
}
}
ins[u]=false;
return true; //全部检查完毕
}
作者

ce-amtic

发布于

2019-02-25

更新于

2020-12-27

许可协议

CC BY-NC-SA 4.0

评论

Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×