Featured image of post 浅谈差分约束系统

浅谈差分约束系统

差分约束系统

前言

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

所以,重学,开写!

差分约束系统是什么

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

一个差分约束系统形如:

已知

$$ \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;
}

参考文献

结尾

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

溜去做题了。

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

图:

(看起来是两种不同的方式罢了……)

Licensed under CC BY-NC-SA 4.0