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

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)$。

个人理解：

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

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

一些对照

差分约束中的条件三角形不等式中的条件

$x_i$ $dist[y]$

$x_j$ $dist[x]$

$c_k$ $z$

$dist[0]$ 其实就是建立了超级源点

$\left\{ \begin{aligned} x_1 \leq x_3+3 \\ x_2 \leq x_1-5 \\ x_3 \leq x_2-3 \end{aligned} \right.$
以此为例建图

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

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

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

差分约束中的条件	三角形不等式中的条件
$x_i$	$dist[y]$
$x_j$	$dist[x]$
$c_k$	$z$

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

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

$x_1-x_2 \leq c \Leftrightarrow x_1-x_2 \geq -c \Leftrightarrow x_1-x_2 < c+1 \Leftrightarrow x_1-x_2 > -c-1$

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

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

#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;
}