---

题348.差分约束-acwing-Q362–区间

---

一、题目

二、题解

依题意给定条件约束，很容易意识到是一个可以利用差分约束来解的题目。
构造一个整数集合Z，里头的整数是从[0,50000]中选取，那其实对于Z最少包含了多少个数，我们可以看作前50000个数中至少选了多少个的问题。对此，我们想到了前缀和的思想，由于前缀和S₀=0，所以我们将区间[0,50000]，往后错一位，即[1,50001]，那么对于所求即为前缀和S₅₀₀₀₁，即dist[50001]，又由求最少个数可知本题应求最长路，现在分析不等关系：
1.对于前缀和，显然有S_i>=S_i-1，即连边时从i-1往i连一条长度为0的边
2.对于范围内的某一个数，或者选或者不选，因此可得到不等式S_i-S_i-1<=1，由于要迎合最长路问题，所以将关系化为S_i-1>=S_i-1，即从i往i-1连一条长度为-1的边。
3.区间[a,b]中的整数个数不少于c个，可得为常数约束的不等关系S_b-S_a-1>=c，此关系为差分约束所需的绝对关系。可化为S_b>=S_a-1+c，即从a-1往b连一条长度为c的边。
之后，验证是否存在超级源点，始发后能够走到所有的边，由关系1知，i-1能够走到i，则从0出发，可以走到1，2，…，可以走到所有的边，因此0即为所需。
最后，由于本题最坏情况可以把0~50000所有数都选上，所以一定有解，因此做spfa时可不用判环。
则依据步骤代码如下：

#include <bits/stdc++.h>

using namespace std;

const int maxn=5e4+5,maxm=2e5+2;
const int Inf=0x3f3f3f3f;

int n;
int h[maxn],e[maxm],w[maxm],ne[maxm],idx;
int dist[maxn],book[maxn];

void add(int a,int b,int c)
{
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}

void spfa()
{
    memset(dist,-Inf,sizeof dist);
    memset(book,0,sizeof book);
    queue<int> q;
    q.push(0);
    dist[0]=0;
    book[0]=1;
    while(!q.empty())
    {
        int t=q.front();
        q.pop();
        book[t]=0;
        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(dist[j]<dist[t]+w[i])
            {
                dist[j]=dist[t]+w[i];
                if(!book[j])
                {
                    q.push(j);
                    book[j]=1;
                }
            }
        }
    }
    return;
}

int main()
{
    scanf("%d",&n);
    memset(h,-1,sizeof h);
    for(int i=1;i<=50001;i++)//[0,50000]为迎合前缀和，所以往后平移了一个单元
    {
        add(i-1,i,0);//i-1->i  0
        add(i,i-1,-1);//i->i-1  -1
    }
    for(int i=0;i<n;i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        a++,b++;//[0,50000]为迎合前缀和，所以往后平移了一个单元
        add(a-1,b,c);//a-1->b  c
    }
    spfa();
    cout<<dist[50001];
}
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

三、有关差分约束

---