首页 算法 图论

# 差分约束问题

差分约束是一种特殊的 N 元一次不等式组。包含 N 个变量X1∼XNX_1 \sim X_N，以及 M 个约束条件，其中每个约束条件有两个变量做差构成，形如：Xi−Xj<=CkX_i-X_j<=C_k，我们要做的就是求出一组X1∼XNX_1 \sim X_N 的值，使得 M 个约束条件全部满足。

例如：

{x1≤x2+1x2≤x3+3x3≤x1−2\left\{\begin{matrix} x_1 \le x_2+1 \\x_2 \le x_3+3 \\x_3 \le x_1-2 \end{matrix}\right.

一组可行的解是：

{x1=0x2=−1x3=−2\left\{\begin{matrix} x_1 = 0 \\x_2 = -1 \\x_3 = -2 \end{matrix}\right.

# 求解差分约束

# 模型分析

考虑一下差分约束的表达形式：Xi−Xj<=CkX_i-X_j<=C_k，我们如果变形成 Xi<=Xj+CkX_i<=X_j + C_k，就可以发现和图论问题求最短路时候的三角不等式非常相似。

回顾一下求最短路的更新规则。假如有一条边，由点 i -> j ，边的权重是 c ，由 dist 数组表示最短路径，那么更新规则是：

if (dist[j] > dist[i] + c) 
    dist[j] = dist[i] + c

所以，根据更新规则，当我们求完整个最短路的时候，公式 dist[j] <= dist[i] + c 对于所有的边都一定成立，因为不成立的话就会把右边的值更新给左边。

由此，我们就可以把差分约束问题转换为最短路问题，对于每个差分约束中的不等式Xi<=Xj+CkX_i<=X_j + C_k ，我们都可以转换成由 点 j 到 点 i 连接一条边，边权是 C。

使用这种转换规则，我们就把整个不等式方程组转换成了一个图，然后对整个图做一个单源最短路算法，如果图中不存在环（方程组无解），那么我们就能找到一组解。

这里还有一点需要注意，后文，我们所有说的不等式，均是已经求完最短路或者最长路之后，所满足的三角不等式。尤其是在后文最大值最小值部分，一定要牢记这一点，否则容易懵圈。

# 源点选择

根据我们以前的内容，最短路算法都是需要一个源点的，那么，从差分约束转换的图，应该如何选择源点呢？

其实认真考虑一下就可以发现，只要源点最终可以到达所有点就可以了，这样我们做完最短路算法，才能保证更新出所有的最短路径，而没有遗漏。

# 图中存在负环会如何？

现在，我们考虑一下转换后图中存在负环会是什么情况。

根据图中推导的最终结果，我们可以得到结论：如果图中存在负环，则说明不等式组矛盾，也就是不等式组无解。

# 求解步骤

  1. 将所有不等式Xi<=Xj+CkX_i<=X_j + C_k ，转换成由 点 j 到 点 i 连接一条边，边权是 C。
  2. 找到一个超级源点，使得该源点最终可以到达所有边。
  3. 从这个超级源点，做一遍最短路算法。
  4. 最终我们会得到两种结果：
    1. 图中存在负环，不等式无解；
    2. 图中不存在负环，最短距离数组 dist[i] ，即是不等式组的一组可行解。
  5. 与最短路相对应的，也可以通过最长路求出一组可行解，最长路时，则通过正环判断是否有解。

# 求可行解的最大值或者最小值

# 前提条件

如果要求最大值或者最小值，则一定有一个不等式是绝对条件，比如：xi>=cx_i>=c 或者 xi<=cx_i<=c 等，如果没有这种绝对条件，则每个变量xix_i 都是参照其他变量，那么就没有绝对的最大值或者最小值。

# 绝对条件如何转换成图中的路径

假设，当前的不等式是xi>=cx_i>=c ，使用超级源点的思路。我们可以虚拟出一个超级源点 0 ，然后从 0 到点 i 连接一条边，边权为 c 。

# 求解步骤

  1. 对于每个xix_i，我们都找到所有由它开始组成的不等式链。

    不等式链：对于任意xix_i，我们从xix_i 开始寻找不等式关系。

    比如有以下不等式关系：xi<=xj+c1x_i<=x_j+c_1，xj<=xk+c2x_j<=x_k+c_2，xk<=5x_k<=5，则我们沿着xix_i 出发，就能找到一条不等式链：
    xi<=xj+c1<=xk+c2+c1<=5+c2+c1x_i<=x_j+c_1<=x_k+c_2+c_1<=5+c_2+c_1。

    需要注意的是，根据我们的前提条件，求最值一定会有绝对条件，使得我们最后可以找到一个常数来做参照。

    那么，对于任意xix_i 形成的不等式链，最后一定可以走到一个只包含常数的式子（即，例子中的5+c2+c15+c_2+c_1），这个常数式子就对应了图中的一条路径（即，例子中 xk−>xj−>xix_k -> x_j -> x_i）。

  2. 对于xix_i 当我们找到它的所有不等式链的解之后，我们可能会得到这样的方程组：

{xi<=2xi<=3xi<=5\left\{\begin{matrix} x_i <= 2 \\x_i <= 3 \\x_i <= 5 \end{matrix}\right.

  1. 假如，我们求的是xix_i 的最大值，那么显然，对于以上不等式组，我们要取xi<=2x_i <= 2 才能使整个不等式组成立。所以我们得到最终的结论：想求 xix_i 的最大值，那么就要使用最短路，也就是找到所有由 xix_i 开头的路径中，权重最小的路径。

  2. 与 3 中结论相对应的，我们也能用相同的方式推导出求最小值的结论：想求 xix_i 的最小值，那么就要使用最长路，也就是找到所有由 xix_i 开头的路径中，权重最大的路径，可以将 2 中的方程组中所有 “<=<=” 都翻转成 “>=>=”，那么最后要让方程组成立，就必须取最大值 5 。

# AcWing 1169. 糖果

幼儿园里有 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,
输入数据完全随机。

输入样例

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

输出样例

11

# 题目描述

给幼儿园的 N 个小朋友分糖果，要求每个小朋友都能分到糖果，其中，有的小朋友还提出了一些要求，而我们的目标是在满足小朋友要求的情况下，给出老师至少需要准备多少个糖果。

# 题目分析

根据给出的关系，我们可以把这些关系用不等式表达出来（本题要求的是至少，也就是最短路（最小值），所以我们需要使用最长路（最大值）算法，因此符号用 “>=>=”）：

  1. 如果 x=1 ，则 A=B ，那么有 A>=B，B>=A ；
  2. 如果 x=2 ，则 A<B ，那么有 B>=A+1 ；
  3. 如果 x=3 ，则 A>=B ，那么有 A>=B ；
  4. 如果 x=4 ，则 A>B ，那么有 A>=B+1 ；
  5. 如果 x=5 ，则 A<=B ，那么有 B>=A ；

如此，按照上述规则，我们就可以把不等式建立成图。

不过还需要考虑的一个问题是，我们在上面已经讲了求最值，必须有绝对条件，那么本题的绝对条件在哪呢？

其实就是题目中给出的条件 “每个小朋友都能分到糖果”，所以说，每个小朋友分到的糖果数量 x 至少要有一个，也就是 x>=1 。

然后，根据上面所讲，我们建立一个超级源点x0x_0，我们让x0=0x_0=0，就可以把每一个 x 都转换成x>=x0+1x>=x_0+1，也就是让超级源点连接到所有其他的点，而连接所有点，也就意味着从超级源点可以到达所有边（注意这个理论反过来不成立，可以到达任意一个边，不一定能到达任意一点，因为可能有孤立的点）。

如此，我们就把题目中的不等式转换成了图，然后只要从超级源点做一遍最长路算法就可以了。

# Code

#include <iostream>
#include <cstring>
using namespace std;
// 注意边数 M 最坏全是 x=1 的话 需要建两条边 
// 并且超级源点到所有点都连一条边 总共是 3 倍的边数
const int N = 100010, M = 300010;
int n, m;
int h[N], w[M], e[M], ne[M], idx;
long long dist[N];
int cnt[N], q[N];
bool st[N];
void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
bool spfa() {
    memset(dist, -0x3f, sizeof dist);
    memset(st, 0, sizeof st);
    memset(cnt, 0, sizeof cnt);
    int hh = 0, tt = 1;
    st[0] = true;
    dist[0] = 0;
    q[0] = 0;
    while (hh != tt) {
        // 因为求负环超时 所以把队列换成栈
        // 我也不知道为什么 这样可以优化
        // 但是 Y 总说 可以在负环超时的情况下用
        // 其他情况不可用 正常情况用可能会降低速度
        // int t = q[hh ++ ];
        // if (hh == N) hh = 0;
        int t = q[-- tt];
        st[t] = false;
        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]) {
                    // q[tt ++ ] = j;
                    // if (tt == N) tt = 0;
                    q[tt ++ ] = j;
                    st[j] = true;
                }
            }
        }
    }
    return true;
}
int main() {
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);
    for (int i = 0; i < m; i ++ ) {
        int x, a, b;
        cin >> x >> a >> b;
        if (x == 1) add(a, b, 0), add(b, a, 0);
        if (x == 2) add(a, b, 1);
        if (x == 3) add(b, a, 0);
        if (x == 4) add(b, a, 1);
        if (x == 5) add(a, b, 0);
    }
    // 虚拟源点
    for (int i = 1; i <= n; i ++ ) add(0, i, 1);
    if (!spfa()) puts("-1");
    else {
        long long res = 0;
        for (int i = 1; i <= n; i ++ ) res += dist[i];
        printf("%lld\n", res);
    }
    return 0;
}
# AcWing 362. 区间
给定 n 个区间 [ai,bi] 和 n 个整数 ci。
你需要构造一个整数集合 Z，使得 ∀i∈[1,n]，Z 中满足 ai≤x≤bi 的整数 x 不少于 ci 个。
求这样的整数集合 Z 最少包含多少个数。
输入格式
第一行包含整数 n。
接下来 n 行，每行包含三个整数 ai,bi,ci。
输出格式
输出一个整数表示结果。
数据范围
1≤n≤50000,
0≤ai,bi≤50000,
0≤ci≤bi−ai+1

输入样例
5
3 7 3
8 10 3
6 8 1
1 3 1
10 11 1

输出样例
6

# 题目描述
本题的题面比较难懂，其实翻译过来就是给出 n 个区间 [ai, bi] ，对应 n 个 ci，要求我们构造一个整数集合，集合中的每个区间 [ai, bi] 必须有至少 ci 个数，问题是整个集合中至少有多少个数。
而根据题目的范围 0≤ai,bi≤50000 ，我们知道可供选择的区间就是 0~50000 。
# 题目分析
本题可以使用类似前缀和的思路来考虑，假设，我们定义 s [k] 表示 0~k 之间最少需要选出多少个整数。
根据我们文章开头的分析，求 “最少” 应该使用最长路，因此，我们要把找到的不等式都变成 >= 。
那么，根据 s[k] 的定义，我们就能推出来第一个不等式： s[i] >= s[i-1] ，所表示的含义是在 0~k 之间选出来的整数数量 一定 不少于 0~k-1 之间 选出来的整数数量。
再考虑，我们对于给定范围内的每个整数只有两种情况一种是不选，另一种是选，如果选就是集合内整数数量 + 1，不选无影响。那么根据 s [k] 的含义，我们就能推出来另一个不等式： s[k]-s[k-1]<=1 。表示的含义是 0~k 和 0~k-1 之间可选择的元素数量只相差一个元素，也就是 k，那么该不等式的含义就是，选则 k 就是 1 ，不选择 k 就是 0 ，也就是 <=1 。转换成 >= 就是： s[k-1]>=s[k]-1 。
最后一个不等式比较明显，既，题目中给出的条件区间 [ai,bi] 之间必须选择至少 ci 个数，所以有不等式 s[b]-s[a-1]>=c （注意区间两端均是闭区间，必须选择 a-1 ，才能让 a 被可能选择）。
那按照这种方式是否存在一个点可以到达所有的边呢？我们注意观察第一个不等式 s[i] >= s[i-1] ，转换成图就是 i-1 -> i 连接一条权重为 0 的边，因此一定会有一条边从 0 一直连接到最后一个点。
另外，还有一点需要注意的是，前缀和思路中，我们的第一个元素通常是 0，那为了让 s[0]=0 ，我们把所有点，也就是所有 a 和 b 的值均后移一位，把数据范围变成 1~50001 ，因为我们求的是个数，所以这样做不会影响最后结果。
# Code
#include <iostream>
#include <cstring>
using namespace std;
// 边的数量为三个不等式各会连出 5w 条边。
const int N = 500010, M = 150010;
int n;
int dist[N], q[N];
bool st[N];
int h[N], w[M], e[M], ne[M], idx;
void add(int a, int b, int c) {
    w[idx] = c, e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
void spfa() {
    memset(dist, -0x3f, sizeof dist);
    int hh = 0, tt = 1;
    q[0] = 0; // 0 号点入队
    // 从 0 个整数中做选择  那么选的数量也是 0
    dist[0] = 0;
    st[0] = true;
    while (hh != tt) {
        int t = q[hh ++ ];
        if (hh == N) hh = 0;
        st[t] = false;
        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]) {
                    q[tt ++ ] = j;
                    if (tt == N) tt = 0;
                    st[j] = true;
                }
            }
        }
    }
}
int main() {
    memset(h, -1, sizeof h);
    cin >> n;
    for (int i = 1;i <= 50001; i ++ ) {
        add(i - 1, i, 0); // 不等式 1
        add(i, i - 1, -1); // 不等式 2
    }
    while (n -- ) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        // 不等式 3
        a ++, b ++ ;
        add(a - 1, b, c);
    }
    spfa();
    printf("%d\n", dist[50001]);
    return 0;
}
# AcWing 1170. 排队布局
当排队等候喂食时，奶牛喜欢和它们的朋友站得靠近些。
农夫约翰有 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≤104,
1≤L,D≤106

输入样例
4 2 1
1 3 10
2 4 20
2 3 3

输出样例
27

# 题目描述
有一些奶牛，沿着一条直线排队等待喂食，他们的排队顺序就是编号，多个奶牛可能处于相同的位置。有一些奶牛有好感，这些奶牛之间的距离不能超过 L，有一些奶牛互相讨厌，这些奶牛的距离不能小于 D。
问题共有三问：
  1. 不存在满足这些情况的方案，输出 - 1；
  2. 如果 1 号牛和 N 号牛的距离可以无限大，输出 - 2；
  3. 否则，输出满足所有要求情况下，1 号奶牛和 N 号奶牛的最大距离；
# 题目分析
# 建立模型
对比上一个题目，本题的差分约束特征还是比较明显的，题面中就给出了两个明显的约束：
  1. 通过题面 “友好的奶牛距离不超过 L”，可以得到不等式： Xb-Xa<=L ；
  2. 通过题面 “反感的奶牛距离不小于 D”，可以得到不等式： Xb-Xa>=D ；
另外，本题其实还有一个不明显的约束条件，根据题面 “奶牛们沿着一条直线等待喂食”，在直线中，从第 1 号点到 N 号点距离一定是逐渐递增的，所以还有一个不等式是：Xi>=Xi−1X_i>=X_{i-1}（注意，可以取到等号是因因为题目中说明，可能有多个奶牛在一个点）。
而本题因为是要求最大距离，所以应该使用最短路，那么，我们要把不等式符号统一成 <= 。那么统一后，我们就能得到三个不等式：
  1. Xb<=Xa+LX_b<=X_a+L；
  2. Xa<=Xb−DX_a<=X_b-D；
  3. Xi<=Xi+1+0X_i<=X_{i+1}+0；
然后，我们又发现本题是没有明显的给出一个绝对条件用来求最大值。但是注意，所有奶牛是在一条数轴上来计算距离的，所以，我们可以让 所有的奶牛都在数轴中 0 的左面，来给出绝对条件，即，初始化每个奶牛： Xi<=0 ，那么该条件在图中相应的含义就是创建一个超级源点 0，从 0 点到所有的点连接了一条长度为 0 的边。
# 问题一
回头看问题，在第一问中，我们需要判断是否有解，那么根据分析出的差分约束模型，判断图中是否存在负环就可以。
# 问题二
1 号点和 N 号点间的距离是否可以无限大？
该问题中，求的是 N号点 相对于 1号点 来说的距离，也就是相对距离，这个距离要用 xn-x1 来求出，那么我们可以把 1 号点固定在特殊点 0 处（也就是 x1=0 ），那么求这俩点的距离就是 xn-0=xn ，我们就只需要判断 xn 是否可以无限大就行了，就相当于从 1 号点求到 N 号点的最短路径。
# 问题三
根据查分约束模型，求一遍不等式组 转换成的图 中的最短路 就行了。
# Code
实现上，有几个点需要注意：
  1. 奶牛的下标是从 1 开始的，一直到 n；
  2. 超级源点可以不用建出来，只要在 spfa 的时候把所有点都入队，距离设置成 0 就行了。
#include <iostream>
#include <cstring>
using namespace std;
// 边的范围是 不等式 1 边数量 & lt;=1000 不等式 2、3 边各 10000 条
const int N = 1010, M = 30010, INF = 0x3f3f3f3f;
int dist[N], cnt[N], q[N];
bool st[N];
int h[N], w[M], e[M], ne[M], idx;
int n, m1, m2;
void add(int a, int b, int c) {
    w[idx] = c, e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
bool spfa(int s) {
    memset(dist, 0x3f, sizeof dist);
    memset(st, 0, sizeof st);
    memset(cnt, 0, sizeof cnt);
    int hh = 0, tt = 0;
    for (int i = 1; i <= s; i ++ ) {
        q[tt ++ ] = i;
        st[i] = true;
        dist[i] = 0;
    }
    while (hh != tt) {
        int t = q[hh ++ ];
        st[t] = false;
        if (hh == N) hh = 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 true;
                if (!st[j]) {
                    q[tt ++ ] = j;
                    if (tt == N) tt = 0;
                    st[j] = true;
                }
            }
        }
    }
    return false;
}
int main() {
    cin >> n >> m1 >> m2;
    memset(h, -1, sizeof h);
    // 不等式 1
    for (int i = 1; i < n; i ++ ) add(i + 1, i, 0);
    while (m1 -- ) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        // 不等式 2 数据里有些 a 比 b 还大 （不知道是不是问题数据
        if (a > b) swap(a, b);
        add(a, b, c);
    }
    while (m2 -- ) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        // 不等式 3
        if (a > b) swap(a, b);
        add(b, a, -c);
    }
    if (spfa(n)) puts("-1");
    else {
        spfa(1);
        if (dist[n] == INF) puts("-2");
        else printf("%d\n", dist[n]);
    }
    return 0;
}
# AcWing 393. 雇佣收银员
一家超市要每天 24 小时营业，为了满足营业需求，需要雇佣一大批收银员。
已知不同时间段需要的收银员数量不同，为了能够雇佣尽可能少的人员，从而减少成本，这家超市的经理请你来帮忙出谋划策。
经理为你提供了一个各个时间段收银员最小需求数量的清单 R (0),R (1),R (2),…,R (23)。
R (0) 表示午夜 00:00 到凌晨 01:00 的最小需求数量，R (1) 表示凌晨 01:00 到凌晨 02:00 的最小需求数量，以此类推。
一共有 N 个合格的申请人申请岗位，第 i 个申请人可以从 ti 时刻开始连续工作 8 小时。
收银员之间不存在替换，一定会完整地工作 8 小时，收银台的数量一定足够。
现在给定你收银员的需求清单，请你计算最少需要雇佣多少名收银员。
输入格式
第一行包含一个不超过 20 的整数，表示测试数据的组数。
对于每组测试数据，第一行包含 24 个整数，分别表示 R (0),R (1),R (2),…,R (23)。
第二行包含整数 N。
接下来 N 行，每行包含一个整数 ti。
输出格式
每组数据输出一个结果，每个结果占一行。
如果没有满足需求的安排，输出 No Solution。
数据范围
0≤R(0)≤1000,
0≤N≤1000,
0≤ti≤23

输入样例
1
1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
5
0
23
22
1
10

输出样例
1

# 题目描述
一天 24 小时，有一个超市，给定这个超市每个小时所需要的收银员数量，给出 N 个可以用的申请人，每个申请人可以从第 i 个时刻连续工作 8 小时，问最少需要多少个收银员能满足全部时刻所需要的收银员数量。
# 题目分析
本题的题面还是比较清晰的，最后问题是问的 “最少”，所以本题应该是求最长路。
然后根据题目要求 “每个时刻都要满足最小数量的收银员”，所以我们假设 nums [24] 为每个时刻需要的收银员数量，x [] 为每个时刻 需要来的 最少收银员，那么则一定有一个基本的不等式： 0<=x[i]<=nums[i] ，表示的含义是在 t [i] 时刻存在的收银员数量在区间 0~nums [i]。
另外，我们还要计算一个每个时刻 i 存在多少收银员，可以用前面 7 个时刻 来的收银员加上当前时刻来的收银员，就是时刻 i 存在收银员，如果时刻 i 存在的收银员满足条件，它就必须大于等于 R [i]，公式为： x[i-7]+x[i-6]+...+x[i]>=R[i] 。
但是我们发现这个公式和差分约束需要的标准不等式有所区别，它是连续的加法，所以，比较明显的处理连续加法的方式就是使用前缀和。
想使用前缀和就需要把第 0 位空出来，所以我们让 nums[] 和 x[] 的下标均从 1 开始，把 S[] 记作前缀和数组。那么就有公式： s[i]=x[1]+x[2]+...+x[i] ，然后我们用前缀和数组来描述前两个公式：
  1. 0<=x[i]<=nums[i] => 0<=s[i]-s[i-1]<=nums[i] 。
  2. 而对于后面的公式，由于是 1~24 是循环的，所以我们要分步来看，第一部分 i>=8 就比较简单，直接用前缀和公式： s[i]-s[i-8]>=R[i] ；第二部分 0<i<=7 ，我们分两段来看，第一段是 s[24]-s[i+16] 也就是 i 较大的那段，第二段则是 i 较小那段 s[i] ，两段加起来就是 s[i]+s[24]-s[i+16]>=R[i] 。
按照求最长路的思路，把上面的几个公式整理成 “>=” 的：
  1. 0<=s[i]-s[i-1]<=nums[i] => s[i]>=s[i-1]+0 ， s[i-1]>=s[i]-nums[i] ；
  2. 当 i>=8 时， s[i]-s[i-8]>=R[i] => s[i]>=s[i-8]+R[i] ；
  3. 当 i<i<=7 时， s[i]>=s[i+16]-s[24]+R[i] ；
整理之后，我们发现最后一个公式还是不能满足差分约束的不等式模型，所以，我们变通一下，把 s[24] 不当做变量，而是当成一个常量，我们枚举所有 s[24] 的值，根据数据范围，最多只有 1000 个人，所以完全可以进行枚举。
根据本题的最终问题：最少需要多少个收银员满足每个时刻的需求，也就是说问题其实就是 s[24] 最小是多少，因为 s[24] 本身就是所有收银员数量的和。
所以，我们就可以在数据范围 0~1000 之间，枚举出最小的 s [24] 的值，使得题目满足要求即可，因此本题就具有二段性，可以使用二分法来快速找到满足要求的值。
# Code
(这道题，真的可能第二天就写不出来了。)
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
// 24 个点，3 倍的边
const int N = 30, M = 100;
int n;
int h[N], w[M], e[M], ne[M], idx;
int r[N], num[N];
int dist[N], cnt[N], q[N];
bool st[N];
void add(int a, int b, int c) {
    w[idx] = c, e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
// 建图 每个 s24 都要重新建图
void build(int s24) {
    memset(h, -1, sizeof h);
    idx = 0;
    for (int i = 1; i <= 24; i++ ) {
        add(i - 1, i, 0);
        add(i, i - 1, -num[i]);
    }
    for (int i = 8; i <= 24; i ++) add(i - 8, i, r[i]);
    for (int i = 1; i <= 7; i ++ ) add(i + 16, i, r[i] - s24);
    // 固定 24 为常量 就是让 s24 >= 0 + c, s24 <= 0 + c;
    add(0, 24, s24), add(24, 0, -s24);
}
bool spfa(int s24) {
    build(s24);
    memset(dist, -0x3f, sizeof dist);
    memset(cnt, 0, sizeof cnt);
    memset(st, 0, sizeof st);
    dist[0] = 0;
    q[0] = 0; // 超级源点 0 可达其他所有边
    st[0] = true;
    int hh = 0, tt = 1;
    while (hh != tt) {
        int t = q[hh ++ ];
        if (hh == N) hh = 0;
        st[t] = false;
        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] >= 25) return false;
                if (!st[j]) {
                    q[tt ++ ] = j;
                    if (tt == N) tt = 0;
                    st[j] = true;
                }
            }
        }
    }
    return true;
}
int main() {
    int T;
    cin >> T;
    // 本题有多组数据 别忘记初始化
    while (T -- ) {
        memset(h, -1, sizeof h);
        idx = 0;
        for (int i = 1; i <= 24; i ++ ) cin >> r[i];
        cin >> n;
        memset(num, 0, sizeof num); // 多组数据 别忘记清空 num
        for (int i = 0; i < n; i ++ ) {
            int t;
            cin >> t;
            num[t + 1] ++ ; // 前缀和
        }
        int l = 0, r = n;
        while (l < r) {
            int mid = (l + r) >> 1;
            if(spfa(mid)) r = mid;
            else l = mid + 1;
        }
        if(spfa(r)) printf("%d\n", r);
        else puts("No Solution");
    }
    return 0;
}
END
   
 更新于   阅读次数  次
请我喝[茶]~(￣▽￣)~*
A Cat Without Sugar 微信支付
微信支付
A Cat Without Sugar 支付宝
支付宝