跳转至

差分约束

概述

学习差分约束之前，必须了解spfa判负环，👉转spfa

差分约束主要解决两类问题

  • 不等式组的可行解
  • 求最大值或最小值

接下来各通过一道例题来说明是如何解决的

不等式组的可行解

引出

对于一种特殊的n元一次不等式，包含n个变量x[1,2...n]，以及m个约束条件，每个约束条件都是由其中两个变量做差构成的，形如\(x[i]-x[j] \le w\)

我们要解决的问题是:求出一组解满足上述所有不等式

思路

对于不等式，若稍微整理一下，就能变成\(x[i] \le x[j] + w\)

由此会联想到单源最短路中的三角不等式，也就是松弛操作，由此我们可以把每个变量看成一个节点，对于每个不等式\(x[i]\le x[j]+w\)，可以看做\(j\)连向\(i\)的一条权值为\(w\)的有向边，在做最短路时就自动满足了这个不等式。

Note

这里应该可以想到为什么需要先学负环相关知识了吧

若图中存在负环，则上述不等式必然无解

注意，要使所有的条件都得到满足，必须建立一个超级源点，使其能到达所有的点，至于为什么，好好想想就知道。

如果没有这样一个点，那是不是有些不等式不一定被满足呢？

看看例题

例.糖果

题目链接

题目描述

幼儿园里有 N 个小朋友，老师现在想要给这些小朋友们分配糖果，要求每个小朋友都要分到糖果。

但是小朋友们也有嫉妒心，总是会提出一些要求，比如小明不希望小红分到的糖果比他的多，于是在分配糖果的时候， 老师需要满足小朋友们的 K 个要求。

幼儿园的糖果总是有限的，老师想知道他至少需要准备多少个糖果，才能使得每个小朋友都能够分到糖果，并且满足小朋友们所有的要求。

输入格式

输入的第一行是两个整数 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 个小朋友分到的糖果。

小朋友编号从 1 到 N。

输出格式

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

数据范围

\(1≤N<105,\)

\(1≤K≤105,\)

\(1≤X≤5,\)

\(1≤A,B≤N,\)

输入数据完全随机。

输入样例

1
2
3
4
5
6
7
8
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

题解

各个条件其实对应一个又一个不等式，对于相等的情况边权为0即可，注意建立超级源点

代码

 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
82
83
84
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,M=3e5+5;
int head[N],e[M],w[M],ne[M],idx=0;
void add(int a,int b,int c)
{
    e[idx] = b;
    w[idx] = c;
    ne[idx] = head[a];
    head[a] = idx ++;
}
int n,m;
long long dis[N];
bool vis[N];
int cnt[N];
int q[N]; // 用栈,防止spfa过慢
int tt = 0,hh = 0; // tt 是最后一个元素的后一个元素
void spfa(int s)
{
    memset(dis,-0x3f,sizeof(dis));
    memset(cnt,0,sizeof(cnt));
    dis[s] = 0;
    vis[s]=true;
    q[0] = s;
    int count = 0;
    while(hh <= tt){
        int pos = q[tt -- ];
        vis[pos] = false;
        for(int i=head[pos];i!=-1;i=ne[i])
        {
            int j = e[i];
            if(dis[j] < dis[pos] + w[i])
            {
                dis[j] = dis[pos] + w[i];
                cnt[j] = cnt[pos] + 1;
                if (++ count > 100 * n) 
                {
                    cout<<"-1"<<endl;
                    return ;
                }
                if(cnt[j] >= n + 1)
                {
                    cout<<"-1"<<endl;
                    return ;
                }
                if(!vis[j])
                {
                    vis[j] = true;
                    q[++ tt ] = j;
                }
            }
        }
    }
    long long res = 0;
    for(int i=1;i<=n;i++) res += dis[i];
    cout<<res<<endl;
}
int main()
{
    cin>>n>>m;
    memset(head,-1,sizeof(head));
    for(int i=1;i<=m;i++)
    {
        int x,a,b;
        cin>>x>>a>>b;
        if(x == 1)
        {
            add(a,b,0);
            add(b,a,0);
        }
        else if(x == 2)
            add(a,b,1);
        else if(x == 3)
            add(b,a,0);
        else if(x == 4)
            add(b,a,1);
        else if(x == 5)
            add(a,b,0);
    }
    for(int i=1;i<=n;i++)
        add(0,i,1);
    spfa(0);
    return 0;
}

最大化或最小化变量距离

引入

主要解决在一系列不等式条件下最大化或最小化\(x[1]\)到\(x[n]\)的距离

思路

最大化距离问题，实际就是求最短路

从一般情况入手

对于求\(x[i]\)的最大值

假设\(x[i]\le x[j]+c[j] \le x[k]+c[k]+c[j] \le + x[0] + x[1] + x[2] ... + x[j]\)

对于上面的不等式链，\(x[i]\)一定小于上面约束条件的最小值

还不懂？

那就举个更简单的例子

  • \(x[i] \le 3\)
  • \(x[i] \le 5\)
  • \(x[ii] \le 10\)

在这种情况下\(x[i]\)是不是小于等于\(min(3, 5, 10)\)，也就是所有上界的最小值，这下懂了吧

Note

之前的不等式链实际就是一条路径的长度,那路径长度的最小值不就是最短路嘛

知道求最大化问题，最小化问题也就明了了，就是求下界的最大值，反向建边跑最长路就行了

接下来看👇例题

例.排队布局

题目链接

题目描述

当排队等候喂食时，奶牛喜欢和它们的朋友站得靠近些。

农夫约翰有 N 头奶牛，编号从 1 到 N，沿一条直线站着等候喂食。

奶牛排在队伍中的顺序和它们的编号是相同的。

因为奶牛相当苗条，所以可能有两头或者更多奶牛站在同一位置上。

如果我们想象奶牛是站在一条数轴上的话，允许有两头或更多奶牛拥有相同的横坐标。

一些奶牛相互间存有好感，它们希望两者之间的距离不超过一个给定的数 L。

另一方面，一些奶牛相互间非常反感，它们希望两者间的距离不小于一个给定的数 D。

给出 ML 条关于两头奶牛间有好感的描述，再给出 MD 条关于两头奶牛间存有反感的描述。

你的工作是：如果不存在满足要求的方案，输出-1；如果 1 号奶牛和 N 号奶牛间的距离可以任意大，输出-2；否则，计算出在满足所有要求的情况下，1 号奶牛和 N 号奶牛间可能的最大距离。

输入格式

第一行包含三个整数 N,ML,MD。

接下来 ML 行，每行包含三个正整数 A,B,L，表示奶牛 A 和奶牛 B 至多相隔 L 的距离。

再接下来 MD 行，每行包含三个正整数 A,B,D，表示奶牛 A 和奶牛 B 至少相隔 D 的距离。

输出格式

输出一个整数，如果不存在满足要求的方案，输出-1；如果 1 号奶牛和 N 号奶牛间的距离可以任意大，输出-2；

否则，输出在满足所有要求的情况下，1 号奶牛和 N 号奶牛间可能的最大距离。

数据范围

\(2≤N≤1000,\)

\(1≤ML,MD≤10^4,\)

\(1≤L,D≤10^6\)

输入样例

1
2
3
4
4 2 1
1 3 10
2 4 20
2 3 3

输出样例

1
27

题解

建立超级源点，若从0开始跑最短路无解，就输出-1，若有解，看看结果是否为无穷，若是，则输出-2，反之输出最大值，具体见代码

代码

 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
82
83
84
85
86
87
88
89
90
91
// xb - xa <= l  xb <= xa + l
// xb - xa >= d  xa <= xb - d
// xi+1 >= xi    xi <= xi+1
#include<bits/stdc++.h>
using namespace std;
const int N=1005,M=2e4+5;
int head[N],e[M],w[M],ne[M],idx=0;
void add(int a,int b,int c)
{
    e[idx] = b;
    w[idx] = c;
    ne[idx] = head[a];
    head[a] = idx ++;
}
int n;
int m1,m2;
int q[N],tt=0,hh=0;
int dis[N];
bool vis[N];
int cnt[N];
bool spfa(int s)
{
    memset(dis,0x3f,sizeof(dis));
    memset(cnt,0,sizeof(cnt));
    memset(vis,false,sizeof(vis));
    for(int i=1;i<=n;i++)
    {
        q[tt++] = i;
        vis[i]=true;
        //dis[i]=0;
    }
    dis[s]=0;
    //int count = 0;
    while(hh<tt)
    {
        int pos = q[--tt];
        vis[pos] = false;
        for(int i=head[pos];i!=-1;i=ne[i])
        {
            int j = e[i];
            if(dis[j] > dis[pos] + w[i])
            {
                dis[j] = dis[pos] + w[i];
                cnt[j] = cnt[pos] + 1;
                //if(++count > 3 * N) return false;
                if(cnt[j] >= n)
                    return false;
                if(!vis[j])
                {
                    vis[j] = true;
                    q[tt++]=j;
                }
            }
        }
    }
    return true;
}
int main()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    cin>>n>>m1>>m2;
    memset(head,-1,sizeof(head));
    for(int i=1;i<=m1;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        if(a>b) swap(a,b);
        add(a,b,c);
    }
    for(int i=1;i<=m2;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        if(a>b) swap(a,b);
        add(b,a,-c); 
    }
    for(int i=1;i<=n-1;i++)
        add(i+1,i,0); //xi+1 >= xi
    for(int i=1;i<=n;i++) add(0,i,0); // 超级源点
    //add(1,0,0);
    if(!spfa(0)) cout<<"-1"<<endl;
    else 
    {
        spfa(1);
        if(dis[n]==0x3f3f3f3f) cout<<"-2"<<endl;
        else cout<<dis[n]<<endl;
    }
    return 0;
}