差分约束系统用于求解一组特殊的
N元一次不等式组. 它包含了N个变量x1~xn和M个约束条件, 其中每个约束条件形如: \(x_i \leqslant x_j + c_k\) (最短路) , \(x_i \geqslant x_j +c_k\) (最长路)约束条件 \(x_i \leqslant x_j +c_k\) , 可转化为一条有向边 \(j \stackrel{c_k}{\rightarrow} i\) , 最短路中有
dist[i] <= dist[j] + ck
差分约束
(1) 求不等式组的可行解
\(\quad\) 源点需要满足的条件: 从源点出发, 一定可以走到所有的边
\(\quad\) 步骤:
\(\quad\) [1] 先找到每个不等式 \(x_i \leqslant x_j + c_k\) 转化成一条从
j走到i, 长度为ck的边\(\quad\) [2] 找到一个源点, 使得该源点一定可以遍历到所有边
\(\quad\) [3] 从源点求一遍单源最短路
\(\quad\) \(\quad\) 结果1: 如果存在负环, 则原不等式组一定无解
\(\quad\) \(\quad\) 结果2: 如果没有负环, 则
dist[i]就是原不等式组的一个可行解(2) 如果求最大值或者最小值, 这里的最值指的是每个变量的最值
\(\quad\) 结论: 如果求的是最小值, 则应该求最长路; 如果求的是最大值, 则应该求最短路
\(\quad\) 问题: 如何转化 \(x_i \leqslant c\) , 其中
c是一个常数, 这类的不等式\(\quad\) 方法: 建立一个超级源点,
0, 建立 \(0 \stackrel{c}{\rightarrow} i\) 的边\(\quad\) 求
xi的最大值, 即求对xi的所有约束条件中的最小值/ 最小上界 (最短路)
求
最小值:最长路\(\Longrightarrow\)大于号\(\Longrightarrow\) \(x_i \geqslant x_j + c_k\)求
最大值:最短路\(\Longrightarrow\)小于号\(\Longrightarrow\) \(x_i \leqslant x_j + c_k\)
当存在负环/ 正环时,
spfa用栈处理比用堆处理更快
//spfa判断是否有正环(栈实现)
//单源最长路,求最小值
bool spfa ()
{
int hh=0,tt=1;
memset(dist,-0x3f,sizeof dist);
dist[0]=0;
q[0]=0;
st[0]=true;
while(hh!=tt)
{
int t=q[--tt];
st[t]=false;
for(int i=h[t];i!=-1;i=ne[i])
{
int j=e[i];
if(dist[j]<dist[t]+w[i])
{
dist[j]=dist[t]+w[i];
cnt[j]=cnt[t]+1;
if(cnt[j]>=n+1)return true; //包含源点0
if(!st[j])
{
q[tt++]=j;
st[j]=true;
}
}
}
}
return false;
}
//spfa判断是否有负环(堆实现)
//单源最短路,求最大值
bool spfa ()
{
int hh=0,tt=1;
memset(dist,0x3f,sizeof dist);
dist[0]=0;
q[0]=0;
st[0]=true;
while(hh!=tt)
{
int t=q[hh++];
if(hh==N)hh=0;
st[t]=true;
for(int i=h[t];i!=-1;i=ne[i])
{
int j=e[i];
if(dist[j]>dist[t]+w[i])
{
dist[j]=dist[t]+w[i];
cnt[j]=cnt[t]+1;
if(cnt[j]>=n+1)return true; //包含源点0
if(!st[j])
{
q[tt++]=j;
if(tt==N)tt=0;
st[j]=true;
}
}
}
}
return false;
}