当前位置：首页 > article >正文

图论——差分约束

article 2025/3/13 5:24:03

差分约束

差分约束是一类特殊的不等式约束问题，其形式为 $x_i \leq x_j + c$ ，其中 $x_i, x_j$ 为变量， $c$ 为常数。这类问题可以通过转换为单源最短路问题来求解其可行解。

我们证明一个差分约束和一个最短路问题是等价的：
1.假设我们已经通过最短路算法求出了一个图中从源点 $s$ 到所有节点的最短路径 $d i s t [i]$ ，根据最短路的松弛性质，对于任意一条边 $\to i, w$ ，都有 $\leq dist[j] + w$ ，因此，最短路的解满足所有的边权约束条件。由此，一个最短路问题对应了一组差分约束问题的不等式组。
2.将差分约束 $x_i \leq x_j + w$ 映射为一条从 $j$ 到 $i$ 的边，权值为 $w$ 。构造图后，通过单源最短路算法求得从某个源点到所有节点的最短距离 $d i s t [i]$ ，可以证明该最短距离是满足差分约束的不等式组的一个解。
综上，一个差分约束和一个最短路问题是等价的。

1.求不等式的可行解
源点需要满足的条件：从源点出发，一定能走到所有的边。

走到所有边等价于所有条件都会被满足，如果没有走到所有边就说明存在没有被满足的条件，不允许。走到所有边不等价于走遍所有点，如果存在孤立的点则说明不存在和他相关的约束，也正因此不用去管它。

步骤：
1.先将每个不等式 $x_i\leq x_j+c_k$ 转换为一条从 $x_j$ 走向 $x_i$ ,长度为 $c_k$ 的边。
2.找一个超级源点，使得该源点一定能遍历到所有边。
3.从源点求一遍单源最短路
结果1：如果存在负环，则原不等式组一定无解。
接过2：如果没有负环，则 $d i s t [i]$ 就是原不等式组的一个可行解。
2.如何求最大值或最小值(每个变量的最值)
结论：如果求的是最小值，则应该求最长路，如果求的是最大值，则应该求最短路。

如果我们想要求最小值，那么一定是要去找下界的，其中一个下界对应的是一条从源点到该节点的路线，为了满足要求，我们要在所有下界中找一个最大值,也正因此我们要求最长路。求最大值同理。
以求 $x_i$ 的最大值为例：求所有从 $x_i$ 出发，构成不等式链 $x_i \leq x _j + c_1 \leq x_k+c_2+c_1 \leq ...\leq c_1+c_2+...$ 所计算出的上界，最终 $x_i$ 的最大值等于所有上界的最小值。

问题：如何转化 $x_i \leq c$ ，其中c是一个常数，这类的不等式。
方法：建立一个超级源点0，然后建立 $0\to i$ ,长度是 $c$ 的边即可。

[SCOI2011] 糖果

题目描述

幼儿园里有 $N$ 个小朋友， $\text{lxhgww}$ 老师现在想要给这些小朋友们分配糖果，要求每个小朋友都要分到糖果。但是小朋友们也有嫉妒心，总是会提出一些要求，比如小明不希望小红分到的糖果比他的多，于是在分配糖果的时候， $\text{lxhgww}$ 需要满足小朋友们的 $K$ 个要求。幼儿园的糖果总是有限的， $\text{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$ 个小朋友分到的糖果；

输出格式

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

样例 #1

样例输入 #1

样例输出 #1

提示

对于 $30\%$ 的数据，保证 $N\leq100$

对于 $100\%$ 的数据，保证 $N\leq100000$

对于所有的数据，保证 $K\leq100000, 1\leq X\leq5, 1\leq A, B\leq N$

$\text{upd 2022.7.6}$ ：新添加 $21$ 组 Hack 数据。

题中的不等关系如下,同时本题要求的是最小值，所以需要求最长路径。
$1,x_i=x_j\to x_i\geq x_j, x_j\geq x_i$
$2,x_i<x_j\to x_j\geq x_i+1$
$3,x_i\geq x_j$
$4,x_i> x_j\to x_i\geq x_j + 1$
$5,x_i\leq x_j\to x_j \geq x_i$
$x_i\geq 1\to x_i \geq x_0+1$
我们根据以上关系进行建图。
0号节点出发可以走到所有点，所以必然能走遍所有边，我们把0号节点作为源点走一遍spfa。
存在负环则无解，反之计算 $d i s t [i]$ $之和。

#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;
const int N = 100010, M = 300010;
int h[N], w[M], e[M], ne[M], tot;
ll dist[N];
bool st[N];
int cnt[N];
int q[N];
int n, m;
void add(int a, int b, int c)
{
    e[tot] = b, ne[tot] = h[a], w[tot] = c, h[a] = tot ++ ;
}
bool spfa()
{
    memset(dist, -0x3f, sizeof dist);
    memset(st, 0, sizeof st);
    int hh = 0, tt = 1;
    q[hh] = 0;
    dist[0] = 0;
    st[0] = 1;
    while (hh != tt)
    {
        int t = q[-- tt];
        st[t] = 0;
        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if (dist[j] < dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                cnt[j] = cnt[t] + 1;
                if (cnt[j] == n + 1) return false;
                if (st[j]) continue;
                q[tt ++ ] = j;
                st[j] = 1;
            }
            
        }
    }
    return true;
}
int main()
{
    cin >> n >> m;
    memset(h, -1, sizeof h);
    while (m -- )
    {
        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 add(a, b, 0);
    }
    for (int i = 1; i <= n; i ++ ) add(0, i, 1);
    if (!spfa()) cout << -1 << endl;
    else{
        ll res = 0;
        for (int i = 1; i <= n; i ++ )
            res += dist[i];
        cout << res << endl;
    }
    return 0;
}

acwing362.区间问题

题目描述

给定 $n$ 个区间 $a_i, b_i]$ 和 $n$ 个整数 $c_i$ 。

你需要构造一个整数集合 $Z$ ，使得对于所有 $\in [1, n]$ ，集合 $Z$ 中满足 $a_i \leq x \leq b_i$ 的整数 $x$ 不少于 $c_i$ 个。

求这样的整数集合 $Z$ 最少包含多少个数。

输入格式

第一行包含整数 $n$ 。
接下来 $n$ 行，每行包含三个整数 $a_i, b_i, c_i$ 。

输出格式

输出一个整数，表示结果。

数据范围

$\leq n \leq 50000$
$\leq a_i, b_i \leq 50000$
$\leq c_i \leq b_i - a_i + 1$

输入样例

输出样例

我们这里采用前缀的的思想，因为区间范围为 $[0, 50000]$ ,包括了0位置，为了能空出来 $s [0] = 0$ ,所以我们把区间整体往右挪一个，变成 $[1, 50001] 。$ 我们用 $s [i]$ 表示 $Z$ 在 $1$ 到 $i$ 中选择的数的个数,最终要求的答案就是 $s [50001]$ 的最小值，所以我们要求最长路。
$s_i\geq s_{i-1}$
$s_i-s_{i-1}\leq 1\to s_{i-1}\geq s_i -1$
$s_b-s_{a-1}\geq c\to s_b\geq s_{a-1}+c$
我们根据以上关系进行建图。
0号节点出发可以走到所有点，所以必然能走遍所有边，我们把0号节点作为源点走一遍spfa。
$s [50001]$ 即为答案。

#include <iostream>
#include <cstring>
using namespace std;
const int N = 50010, M = 150010;
int h[N], e[M], ne[M], w[M], tot;
int dist[N];
bool st[N];
int q[N];
int n;
void add(int a, int b, int c)
{
    e[tot] = b, ne[tot] = h[a], w[tot] = c, h[a] = tot ++ ;
}
void spfa()
{
    memset(dist, -0x3f, sizeof dist);
    int hh = 0, tt = 1;
    dist[0] = 0;
    q[0] = 0;
    st[0] = 1;
    while (hh != tt)
    {
        int t = q[hh ++ ];
        if (hh == N) hh = 0;
        st[t] = 0;
        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if (dist[j] < dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                if (!st[j])
                {
                    st[j] = 1;
                    q[tt ++ ] = j;
                    if (tt == N) tt = 0;
                }
            }
        }
    }
    return ;
}
int main()
{
    cin >> n;
    memset(h, -1, sizeof h);
    for (int i = 1; i <= 50001; i ++ )
    {
        add(i - 1, i, 0);
        add(i, i - 1, -1);
    }
    for (int i = 1; i <= n; i ++ )
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b + 1, c);
    }
    spfa();
    cout << dist[50001];
    return 0;
}

acwing1170.排队布局

题目描述

农场里有 N 头奶牛，编号从 1 到 N，沿一条直线排队等待喂食。奶牛排队的顺序和编号相同。奶牛喜欢与它们的朋友靠近，但也有一些奶牛互相反感，不希望太靠近。

有些奶牛希望与它们的朋友之间的距离不超过一个给定的值 L，另一些奶牛希望它们之间的距离至少为 D。你的任务是：给定这些限制条件，计算在满足所有要求的情况下，1 号奶牛与 N 号奶牛之间可能的最大距离。如果无法满足这些条件，输出 -1；如果 1 号奶牛和 N 号奶牛的距离可以任意大，输出 -2。

输入格式

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

接下来的 ML 行，每行包含三个正整数 A, B, L，表示奶牛 A 和奶牛 B 之间的距离不能超过 L。

接下来的 MD 行，每行包含三个正整数 A, B, D，表示奶牛 A 和奶牛 B 之间的距离必须至少为 D。

输出格式

输出一个整数。如果没有满足条件的方案，输出 -1。如果 1 号奶牛和 N 号奶牛的距离可以任意大，输出 -2；否则，输出在满足所有要求的情况下，1 号奶牛和 N 号奶牛之间可能的最大距离。

样例输入

样例输出

挖掘题目中的不等关系：
$x_i\leq x_{i+1} \to x_i\leq x_{i+1}+0$
$x_b-x_a\leq L\to x_b\leq x_a+L$
$x_b-x_a\geq D\to x_a \leq x_b -D$
对于第一个问题，我们从n号结点出发判断是否存在负环即可。
对于第二第三个问题，我们从1号节点出发，如果到n号节点的距离是0x3f3f3f3f,则说明距离可以任意大，反之输出dist[n]即可。

#include <iostream>
#include <cstring>
using namespace std;
const int N = 1010, M = 21010;
int h[N], w[M], e[M], ne[M], tot;
int dist[N];
bool st[N];
int cnt[N];
int q[N];
int n, m1, m2;
void add(int a,int b, int c)
{
    e[tot] = b, ne[tot] = h[a], w[tot] = c, h[a] = tot ++ ;
}
bool spfa(int sz)
{
    memset(st, 0, sizeof st);
    memset(cnt, 0, sizeof cnt);
    memset(dist, 0x3f, sizeof dist);
    int hh = 0, tt = 0;
    for (int i = 1; i <= sz; i ++ )
    {
        q[tt ++ ] = i;
        st[i] = 1;
        dist[i] = 0;
    }
    while (hh != tt)
    {
        int t = q[hh ++ ];
        if (hh == N) hh = 0;
        st[t] = 0;
        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                cnt[j] = cnt[t] + 1;
                if (cnt[j] >= n) return false;
                if (!st[j])
                {
                    st[j] = 1;
                    q[tt ++ ] = j;
                    if (tt == N) tt = 0;
                }
            }
        }
    }
    return true;
}
int main()
{
    cin >> n >> m1 >> m2;
    memset(h, -1, sizeof h);
    for (int i = 1; i < n; i ++ ) add(i + 1, i, 0);
    while (m1 -- )
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }
    while (m2 -- )
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(b, a ,-c);
    }
    if (!spfa(n)) cout << -1 << endl;
    else{
        spfa(1);
        if (dist[n] == 0x3f3f3f3f) cout << -2 << endl;
        else cout << dist[n] << endl;
    }
    return 0;
}

acwing393. 雇佣收银员

一家超市要每天24小时营业，为了满足营业需求，需要雇佣一大批收银员。已知不同时间段需要的收银员数量不同，为了能够雇佣尽可能少的人员，从而减少成本，这家超市的经理请你来帮忙出谋划策。经理为你提供了一个各个时间段收银员最小需求数量的清单 $R (0), R (1), R (2), \dots, R (23)$ 。 $R (0)$ 表示午夜00:00到凌晨01:00的最小需求数量， $R (1)$ 表示凌晨01:00到凌晨02:00的最小需求数量，以此类推。一共有N个合格的申请人申请岗位，第i ii个申请人可以从 $t_i$ 时刻开始连续工作8小时。收银员之间不存在替换，一定会完整地工作8小时，收银台的数量一定足够。现在给定你收银员的需求清单，请你计算最少需要雇佣多少名收银员。

输入格式：

第一行包含一个不超过 $20$ 的整数，表示测试数据的组数。对于每组测试数据，第一行包含24个整数，分别表示 $R (0), R (1), R (2), \dots, R (23)$ 。第二行包含整数N。接下来N行，每行包含一个整数 $t_i$ 。

输出格式：

每组数据输出一个结果，每个结果占一行。如果没有满足需求的安排，输出No Solution。

数据范围：

$0 \leq R (0) \leq 100$
$0 \leq N \leq 1000$
$0 ≤ t_i ≤ 23$

根据题意可挖掘以下约束关系：
$num[i]\geq x_i\geq 0$
$i\geq 7:x_i+x_{i-1}+...+x_{i-7}\geq r_i$
$7:x_0+x_1+...+x_{i+17}+...+x_{23}\geq r_i$
这里我们使用前缀和，因为0号位置已被占用，所以整体往后挪一位。
$S_i\geq S_{i-1}+0$
$S_{i-1}\geq S_i-num[i]$
$i\geq 8:S_i\geq S_{i-8}+r_i$
$8:S_{i}\geq S_{i+16}-S_{24}+r_i$
在最后一个公式中，右边存在变量，我们考虑从前往后枚举 $S_{24}$ 的值，第一个不存在负环的位置就是答案。
因为限制了 $S_{24}=c$ ，所以需要考虑约束条件 $S_{24}\geq x_0+c,x_0\geq S_{24}-c$ 。

 #include <iostream>
 #include <cstring>
 using namespace std;
 const int N = 30, M = 100;
 int h[N], w[M], e[M], ne[M], tot;
 int r[N];
 int dist[N];
 bool st[N];
 int cnt[N];
 int num[N];
 int q[N];
 int n, t;
 void add(int a, int b, int c)
 {
    e[tot] = b, w[tot] = c, ne[tot] = h[a], h[a] = tot ++ ;
 }
 void build(int s24)
 {
    memset(h, -1, sizeof h);
    tot = 0;
    for (int i = 1; i <= 24; i ++ )
    {
        add(i - 1, i, 0);
        add(i, i - 1, - num[i]);
        if (i >= 8) add(i - 8, i, r[i]);
        else add(i + 16, i, r[i] - s24);
    }
    add(0, 24, s24);
    add(24, 0, -s24);
    return ;
 }
 bool spfa(int s24)
 {
    build(s24);
    memset(dist, -0x3f, sizeof dist);
    memset(st, 0, sizeof st);
    memset(cnt, 0, sizeof cnt);
    int hh = 0, tt = 1;
    q[0] = 0;
    st[0] = 1;
    dist[0] = 0;
    while (hh != tt)
    {
        int t = q[hh ++ ];
        if (hh == N) hh = 0;
        st[t] = 0;
        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if (dist[j] < dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                cnt[j] = cnt[t] + 1;
                if (cnt[j] == 26) return false;
                if (!st[j])
                {
                    st[j] = 1;
                    q[tt ++ ] = j;
                    if (tt == N) tt = 0;
                }
            }
        }
    }
    return true;
 }
 int main()
 {
    cin >> t;
    while (t -- )
    {
        memset(num, 0, sizeof num);
        for (int i = 1; i <= 24; i ++ )
            cin >> r[i];
        cin >> n;
        for (int i = 1; i <= n; i ++ )
        {
            int t;
            cin >> t;
            num[t + 1] += 1;
        }
        bool flag = 0;
        for (int i = 0; i <= 1000; i ++ )
        {
            if (spfa(i))
            {
                flag = 1;
                cout << i << endl;
                break;
            }
        }
        if (!flag) cout << "No Solution" << endl;
    }
    return 0;
 }