差分约束系统

给定若干组形如$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. 正权环：一个正权环在最短路中至多被经过一次。因为当绕这个环第二圈时，只会让走过的路径增大，并且这种增大总是无意义的。
2. 零权环：相似于正权环，零权环至多被经过一次。因为它并不能使最短路改变。
3. 负权环：对于一个包含负权环的图，不存在最短路。因为只要在负环中无限转圈，就可以让路径无限变短。

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

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

2 SPFA求解差分约束

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$次才可以判定。

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

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; //全部检查完毕
}