差分约束系统

前言

真的好久好久都没打过这个算法了。当时学的时候学得不明不白，又不写总结、又不刷题（我都不知道自己咋想的），所以今天刷图论题的时候，发现一车子的差分约束都没打过。

所以，重学，开写！

差分约束系统是什么

不要被他名字的学术性吓到了，这个“系统”字面意思理解就行，不是什么高深庞大的东西。

一个差分约束系统形如：

已知

$$ \begin{cases} x_{c_1}-x_{c'_1}\leq y_1 \\x_{c_2}-x_{c'_2} \leq y_2 \\ \cdots\\ x_{c_m} - x_{c'_m}\leq y_m\end{cases} $$

求这个不等式组任意的一组解。

其实说白了，就是 $n$ 个变量，$m$ 个约束条件（$x_i-x_j\leq y_k$）。

怎么解决这个系统

怎么解这个不等式？

首先移项一手：

$$ x_i\leq x_j+y_k $$

你看，是不是和图论中的 $dis_v\leq dis_u+w_i$ 很像啊？

所以这个问题可以转换成一个最短路问题——把 $j$ 向 $i$ 连一条权值为 $y_k$ 的边。

可是这个图并不一定连通，所以我们建一个超级源点 $0$。带入到系统中，便是增加了 $n$ 个约束条件：$x_i\leq x_0$。如此，整个系统得到完善。

然后就家常便饭，直接最短路。如果存在负环，不等式组无解；否则可以得到每个点的 $dis_i$。而不等式的一组可行解，正是 $x_i=dis_i$。

负环怎么判

这里稍微讲一手。

首先为什么出现负环就无解？

因为最短路算法，就是不断走边权最小的边，以更新每个点到源点的最短距离。但如果存在一个环，且总权为负，那么就可以一直走、一直走，直至边权 $=-\infin$。

现在，原图共 $n+1$ 个点，如果不存在负环，那么最短路中每个点肯定只会进队一次。因为没有必要经过两次去松弛它的邻接点。

所以如果 $n$ 轮松弛结束后仍然存在可松弛的边，那就一定存在负环。

在题目中如何用差分约束算法

如果在模版题，就不多说了。

我们对于题目中的关系，可以得到一些不等条件，再化简成一般形式 $x_i\leq x_j+y_k$，就可以建立这样一个差分约束系统。

如果是相等情况怎么办？

简单，直接拆分成 $x_i\leq x_j+y_k$ 与 $x_j\leq x_i+y_k$ 这两条约束条件。

P5960【模板】差分约束

code

 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
64


#include<bits/stdc++.h>
using namespace std;

#define int long long

const int MAXN=1e4+5;

int n,m;
int dis[MAXN],cnt[MAXN];
bool vis[MAXN];
int su,en[MAXN],lt[MAXN],hd[MAXN],vl[MAXN];

void add(int u,int v,int w)
{
    en[++su]=v,vl[su]=w,lt[su]=hd[u],hd[u]=su;
}

bool SPFA(int s)
{
    queue<int> q;
    memset(dis,0x3f,sizeof(dis));
    vis[s]=1,dis[s]=0;
    q.push(s);
    while (!q.empty())
    {
        int u=q.front();q.pop();
        for(int i=hd[u];i;i=lt[i])
        {
            int v=en[i];
            if(dis[v]>dis[u]+vl[i])
            {
                dis[v]=dis[u]+vl[i];
                if(!vis[v])
                {
                    vis[v]=1,cnt[v]++;
                    if(cnt[v]>n) return 0;
                    q.push(v);
                }
            }
        }
        vis[u]=0;
    }
    return 1;
}

signed main()
{
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++)
        add(0,i,0); // 超级源点
    for(int i=1,u,v,w;i<=m;i++)
    {
        scanf("%lld%lld%lld",&u,&v,&w);
        add(v,u,w); // 注意这里是 v --w-> u 
    }
    if(!SPFA(0))
        puts("NO");
    else
    {
        for(int i=1;i<=n;i++)
            printf("%lld ",dis[i]);
    }
    return 0;
}

参考文献

[1] StudyingFather，题解 P5960 【【模板】差分约束算法】

结尾

如果想看图论相关文章，刚好我 2 年前写了一篇。虽然年代久远，格式、文笔也很垃坤，但是得看且看吧。

溜去做题了。

如果你想问为什么有些题目用的差分约束是跑最长路，这个我还不能回答你（我也不知道），但是可以先放张图，等我学会后再回来更（当然也可能忘记了，如果你正在看，可以在评论区踢我）。

图：

（看起来是两种不同的方式罢了……）