小指针

V1

2022/09/09阅读:27主题:凝夜紫

【图论专题】差分约束问题的常规思路

外部链接公众号无效,点击左下角“阅读原文”传送到我的博客获得更好的阅读体验。

差分约束问题

差分约束是一种特殊的N元一次不等式组。包含N个变量 ,以及M个约束条件,其中每个约束条件有两个变量做差构成,形如: ,我们要做的就是求出一组 的值,使得M个约束条件全部满足。

例如:

一组可行的解是:

求解差分约束

模型分析

考虑一下差分约束的表达形式: ,我们如果变形成 ,就可以发现和图论问题求最短路时候的三角不等式非常相似。

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

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

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

由此,我们就可以把差分约束问题转换为最短路问题,对于每个差分约束中的不等式 ,我们都可以转换成由 点j 到 点i 连接一条边,边权是C

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

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

源点选择

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

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

图中存在负环会如何?

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

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

求解步骤

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

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

前提条件

如果要求最大值或者最小值,则一定有一个不等式是绝对条件,比如: 或者 等,如果没有这种绝对条件,则每个变量 都是参照其他变量,那么就没有绝对的最大值或者最小值。

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

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

求解步骤

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

    不等式链:对于任意 ,我们从 开始寻找不等式关系。

    比如有以下不等式关系: ,则我们沿着 出发,就能找到一条不等式链:

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

    那么,对于任意 形成的不等式链,最后一定可以走到一个只包含常数的式子(即,例子中的 ),这个常数式子就对应了图中的一条路径(即,例子中 )。

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

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

  2. 与3中结论相对应的,我们也能用相同的方式推导出求最小值的结论:想求 的最小值,那么就要使用最长路,也就是找到所有由 开头的路径中,权重最大的路径,可以将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

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

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

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, -0x3fsizeof dist);
    memset(st, 0sizeof st);
    memset(cnt, 0sizeof 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 + 1return 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, -1sizeof 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~k0~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, -0x3fsizeof 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, -1sizeof 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号点距离一定是逐渐递增的,所以还有一个不等式是: (注意,可以取到等号是因因为题目中说明,可能有多个奶牛在一个点)。

而本题因为是要求最大距离,所以应该使用最短路,那么,我们要把不等式符号统一成<= 。那么统一后,我们就能得到三个不等式:

然后,我们又发现本题是没有明显的给出一个绝对条件用来求最大值。但是注意,所有奶牛是在一条数轴上来计算距离的,所以,我们可以让 所有的奶牛都在数轴中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 边数量<=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, 0x3fsizeof dist);
    memset(st, 0sizeof st);
    memset(cnt, 0sizeof 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, -1sizeof 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]+0s[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, -1sizeof 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(024, s24), add(240, -s24);
}

bool spfa(int s24) {
    build(s24);
    memset(dist, -0x3fsizeof dist);
    memset(cnt, 0sizeof cnt);
    memset(st, 0sizeof 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] >= 25return 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, -1sizeof h);
        idx = 0;
        for (int i = 1; i <= 24; i ++ ) cin >> r[i];
        cin >> n;
        memset(num, 0sizeof 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

分类:

后端

标签:

数据结构与算法

作者介绍

小指针
V1