差分约束例题

发表于
字数统计: 3,344 | 阅读时长 ≈ 14

前言

这几天刷 bzoj 的题，碰到几道差分约束的…
想到博客里还没有这类题目（图论也没有…
所以来填一下这方面的空缺

侵删

简述差分约束

我们来看一下这个看样子很高大上的东西
其实这玩意就是跑最短路的
我觉得最短路不需要进行讲解基本知识嘛
所以我们直接看差分约束的精髓

如果一个系统由 n 个元素 m 个不等式组成，并且每个不等式都是类似于 a - b > c 的（意思就是说长成这样的），把这个不等式移项，我们可以得到 a > b + c ，这表示什么意思呢？
我们把 a , b 都看成一个点，如果满足这条不等式，不就代表 b 到 a 的有向边权值大于 c 吗（同大于等于，小于，小于等于，等于），我们也可以说成 a 到 b 有一条权值小于 -c 的边

因此我们发现，对于每个不等式（只有两个元素），类似于 a[i]-a[j]<=c ,我们可以认为对于节点 j 和 i 建立一条 j -> i 的有向边，且边权为 c 。而如果我们要求点 i 的最短路，即求 a[i] 到 a[0] 的最大值

我们来看一组不等式

  • x1 - x0 <=2 (1)
  • x2 - x0 <=7 (2)
  • x3 - x0 <=8 (3)
  • x2 - x1 <=3 (4)
  • x3 - x2 <=2 (5)

我们先整理出一些数与数关系

  • (3) ： x3 - x0 <= 8
  • (2) + (5) ： x3 - x0 <= 9
  • (1) + (4) + (5) ： x3 - x2 <= 7

所以我们最终可以得到 x3 - x0 <= 7

先把上面内容放在一旁，我们来看一道求最短路的题:

给定四个小岛以及小岛之间的有向距离，问从第0个岛到第3个岛的最短距离。箭头表示有向边，蓝色数字表示权值（画的丑勿介

好了我们有一张很好的图…
这是一道很简单的最短路问题，我们枚举路线，一共有三条

  • 0 -> 3 长度为 8
  • 0 -> 2 -> 3 长度为 7 + 2 = 9
  • 0 -> 1 -> 2 -> 3 长度为 2 + 3 + 2 = 7

所以 x0 到 x3 的距离最小为 7 ，是不是觉得跟上面的不等式有什么关系？
我们结合求单源最短路的方法（ spfa ，Dijkstra ）很容易发现我们一开始讲的差分约束就是一种数形结合的例子，对于每一个不等式，我们都可以相应的建立一条有向边，上面举例的不等式和图就是可以互相转化的（没毛病吧？！
实际上我们接触很频繁的三角不等式，对应的建图

很容易就可以知道 min ( b , a+c ),正好对应 a —> c 的最短路。我们将三个不等式推广到 m 个，变量从 3 个推广到 n 个，就变成 n 个点 m 条边的最短路了

我们现在来看一下解的存在性

我们求一条最短路，在图中可能会存在负环或者到终点不存在连边

  • 因此对应负环，在图中一定是不存在最短路的，这种情况是无解的
  • 如果我们连不到终点，表示起点和终点并没有约束关系，因此这种情况的结果是无限多个解
  • 在实际问题中我们要加以判断，可能会导致不同的输出

综上所述，一个差分约束系统我们有三种解：有解，无解，有无限多解

现在我们来看一下别的不等式情况

  • 如果我们将原先的 <= 变成 >= ，我们求两点之间之差的最小值，求的是两点之间的最长路（数形结合）我们同样可以从三角不等式进行推广
  • 如果给出的不等式有”<=”也有”>=”，又该如何解决呢？很明显，首先需要关注最后的问题是什么，如果需要求的是两个变量差的最大值，那么需要将所有不等式转变成”<=”的形式，建图后求最短路；相反，如果需要求的是两个变量差的最小值，那么需要将所有不等式转化成”>=”，建图后求最长路。
  • 如果存在类似于 a - b = c 的不等式，我们可以转化成 a - b >= c 或者 a - b <= c，再根据实际情况进行建边
  • 另外，如果这些变量都是整数，在遇到形如 a - b > c 的情况，我们不能用小于号建边（因为不等），我们要把它们转变成带等号的不等式，比如 a - b >= c+1

我尽量保持原创，图也是自己画的
差分约束其实很简单说是简述我也写了很多…
所以我们现在来看两道题目

SCOI2011 糖果

题目描述

幼儿园里有N个小朋友，lxhgww老师现在想要给这些小朋友们分配糖果，要求每个小朋友都要分到糖果。但是小朋友们也有嫉妒心，总是会提出一些要求，比如小明不希望小红分到的糖果比他的多，于是在分配糖果的时候，lxhgww需要满足小朋友们的K个要求。幼儿园的糖果总是有限的，lxhgww想知道他至少需要准备多少个糖果，才能使得每个小朋友都能够分到糖果，并且满足小朋友们所有的要求。

输入输出格式

输入格式：

输入的第一行是两个整数N，K。接下来K行，表示这些点需要满足的关系，每行3个数字，X，A，B。如果X=1， 表示第A个小朋友分到的糖果必须和第B个小朋友分到的糖果一样多；如果X=2， 表示第A个小朋友分到的糖果必须少于第B个小朋友分到的糖果；如果X=3， 表示第A个小朋友分到的糖果必须不少于第B个小朋友分到的糖果；如果X=4， 表示第A个小朋友分到的糖果必须多于第B个小朋友分到的糖果；如果X=5， 表示第A个小朋友分到的糖果必须不多于第B个小朋友分到的糖果；

输出格式：

输出一行，表示lxhgww老师至少需要准备的糖果数，如果不能满足小朋友们的所有要求，就输出-1。

输入输出样例

#####输入样例#1： 

5 7
1 1 2
2 3 2
4 4 1
3 4 5
5 4 5
2 3 5
4 5 1

#####输出样例#1： 

11

说明

【数据范围】

对于30%的数据，保证 N<=100

对于100%的数据，保证 N<=100000

对于所有的数据，保证 K<=100000，1<=X<=5，1<=A, B<=N

解题分析

我们发现这道题有很多不等式…
看到不等式我就想到了差分约束
不过这道题的约束条件很多，我们要区分好，不能在建边的时候弄混
used用来判断负环因为一个点不可能被经过超过 n 次
实际上 spfa 是从 0 开始跑的我直接进队列也是一样的…
可能我建边跟网上很多题解不一样反过来也是一样的
对于每次读入情况第二种和第四种 a == b 是要进行特判的
另外不能忘记判负环的情况
计算答案的时候 long long 要开不然会 WA
注意空间开大一点
建议用 BZOJ 跑洛谷数据太水了相同代码BZOJ RE90分洛谷AC…
交代就那么多有什么东西代码里看好了，就是一个 spfa 要小心

AC代码96ms

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
// luogu-judger-enable-o2
#include<cstdio>
#include<cstring>
#include<queue>
#include<cctype>
#define re register int
#define xep(i,x) for(re i=head[x];i;i=nxt[i])
#define ll long long

using namespace std;

const int N=100010;
int n,k,cnt=0;
int head[N<<2],nxt[N<<2],to[N<<2],val[N<<2];
int vis[N],sum[N],used[N];
ll ans=0;
queue < int > q;

inline int read(){
    int X=0,w=0; char ch=0;
    while(!isdigit(ch)) {w|=ch=='-';ch=getchar();}
    while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
    return w?-X:X;
}

inline void add(int x,int y,int v){
    to[++cnt]=y;nxt[cnt]=head[x];
    head[x]=cnt;val[cnt]=v;
}

inline bool spfa(){
    while(!q.empty()){
        int u=q.front();
        vis[u]=0;q.pop();
        xep(i,u){
            int v=to[i];
            if(sum[v]<sum[u]+val[i]){
                sum[v]=sum[u]+val[i];
                used[v]++;
                if(used[v]>n)
                    return 0;
                if(!vis[v]) vis[v]=1,q.push(v); 
            }
        }
    }
    return 1;
}

int main(){
    n=read();k=read();
    while(k--){
        int opt,a,b;
        scanf("%d%d%d",&opt,&a,&b);
        switch(opt){
            case 1:{add(a,b,0);add(b,a,0);break;}
            case 2:{
                if(a==b){
                    puts("-1");return 0;
                }
                add(a,b,1);break;
            }
            case 3:{add(b,a,0);break;}
            case 4:{
                if(a==b){
                    puts("-1");
                    return 0;
                }
                add(b,a,1);break;
            }
            case 5:{add(a,b,0);break;}
        } 
    }
    for(re i=1;i<=n;i++)
        vis[i]=1,sum[i]=1,q.push(i);
    if(!spfa()){
        puts("-1");return 0;
    }
    for(re i=1;i<=n;i++) ans+=sum[i];
    printf("%lld\n",ans);
    return 0;
}

BZOJ3436 小K的农场

题目描述

小K在MC里面建立很多很多的农场，总共n个，以至于他自己都忘记了每个农场中种植作物的具体数量了，他只记得一些含糊的信息（共m个），以下列三种形式描述：
农场a比农场b至少多种植了c个单位的作物，
农场a比农场b至多多种植了c个单位的作物，
农场a与农场b种植的作物数一样多。
但是，由于小K的记忆有些偏差，所以他想要知道存不存在一种情况，使得农场的种植作物数量与他记忆中的所有信息吻合。

输入输出格式

输入格式：

第一行包括两个整数 n 和 m，分别表示农场数目和小 K 记忆中的信息数目。
接下来 m 行：
如果每行的第一个数是 1，接下来有 3 个整数 a,b,c，表示农场 a 比农场 b 至少多种植了 c 个单位的作物。
如果每行的第一个数是 2，接下来有 3 个整数 a,b,c，表示农场 a 比农场 b 至多多种植了 c 个单位的作物。如果每行的第一个数是 3，家下来有 2 个整数 a,b，表示农场 a 终止的数量和 b 一样多。

输出格式：

如果存在某种情况与小 K 的记忆吻合，输出“Yes”，否则输出“No”。

输入输出样例

输入样例#1：
3 3
3 1 2
1 1 3 1
2 2 3 2
输出样例#1：
Yes

说明

对于 100% 的数据保证：1 ≤ n，m，a，b，c ≤ 10000。

解题思路

这道题跟上一道很像
只要搞清楚约束条件，对于一般的差分约束题目还是蛮好解的
相较之下这道题还比较简单，只需要判一下 spfa 是否为真，并不像上一道题一样要统计答案
但是同样洛谷AC大视野RE debug了好久还是洛谷数据水…
实际上就是判负环的时候在 if 里面判…
还是直接上代码好了挺简单的
（我的建边还是和别人不一样…

AC代码2264ms

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
// luogu-judger-enable-o2
#include<cstdio>
#include<cstring>
#include<queue>
#include<cctype>
#define re register int
#define xep(i,x) for(re i=head[x];i;i=nxt[i])
 
using namespace std;

inline int read(){
    int X=0,w=0; char ch=0;
    while(!isdigit(ch)) {w|=ch=='-';ch=getchar();}
    while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
    return w?-X:X;
}

const int N=10010;
int n,m,cnt=0;
int head[N<<2],nxt[N<<2],to[N<<2],val[N<<2];
int sum[N],vis[N],ru[N];
queue < int > q;

inline void add(int x,int y,int v){
    to[++cnt]=y;nxt[cnt]=head[x];
    head[x]=cnt;val[cnt]=v;
}

inline bool spfa(){
    while(!q.empty()){
        int u=q.front();q.pop();
        vis[u]=0;
        xep(i,u){
            int v=to[i];
            if(sum[v]<sum[u]+val[i]){
                sum[v]=sum[u]+val[i];
                ru[i]++;
                if(ru[i]>n) return 0;
                if(!vis[v]) 
                    vis[v]=1,q.push(v);
            }
        }
    }
    return 1;
}

int main(){
    memset(sum,0,sizeof(sum));
    n=read();m=read();
    for(re i=1;i<=m;i++){
        int opt,a,b,c;
        opt=read();a=read();b=read();
        if(opt==1) c=read(),add(b,a,c);
        else if(opt==2) c=read(),add(a,b,-c);
        else if(opt==3) add(a,b,0),add(b,a,0);
    }
    for(re i=1;i<=n;i++)
        vis[i]=1,q.push(i);
    spfa()?puts("Yes"):puts("No");
    return 0;
}

后记

看到很多不等式就要想到差分约束…
想到差分约束转化一下不等式建边还是很容易的
建完边跑最短路或最长路不就很简单了？
所以上面三句话就是差分约束的精髓（滑稽
这东西还是蛮基础也是挺有用的
写了一个多小时也是挺久的手打很累…
也就是因为下午做到了两道模板的差分约束

欢迎指正联系方式如下…

qq： 953559040

微博： IncinblePan

洛谷： SherlockPan