题目描述
给定 \(n\) 个区间 \([a_i,b_i]\) 和 \(n\) 个整数 \(c_i\)。
你需要构造一个整数集合 \(Z\)，使得 \(\forall i \in [1,n]\)，\(Z\) 中满足 \(a_i \le x \le b_i\) 的整数 \(x\) 不少于 \(c_i\) 个。
求这样的整数集合 \(Z\) 最少包含多少个数。
解题思路
\(\qquad\) 根据前缀和思想，我们用\(s[k]\)表示最好选法中，整数集合\(Z\)包含了\(0\sim k\)中的\(s[k]\)个数，那在整数集合中\(a_i\le x\le b_i\)的数也就是\(s[b_i]-s[a_i-1]\ge c_i\)，那我们就可以看出一个差分约束系统，将\(a_i-1\)向\(b_i\)连一条权重为\(1\)的有向边。
\(\qquad\)但是如果要求解，那这一个差分约束的条件不够，应该再找几个：
\(\qquad\qquad\Large a.\)由于\(0\sim k\)中间选的数不会\(0\sim k - 1\)的少，所以\(s[k] - s[k-1]\ge 0\)
\(\qquad\qquad\Large b.\)由于一个数至多只能选一次，所以\(s[k]-s[k-1] \le 1\)，转化成\(s[k-1]-s[k]\ge -1\)
整理上式我们可以得到一个差分约束系统
\[\left \{ \begin{array}c s[b_i]-s[a_i-1]\ge c_i\\ s[k] - s[k-1]\ge 0\\ s[k-1]-s[k]\ge -1 \end{array} \right. \]然后就是求一个\(-1\)到\(50001\)的最长路，为了方便可以把所有下标\(+1\)
代码
#include <iostream>
#include <cstring>
using namespace std;
const int N = 5e4 + 10, M = 3 * N;
int dist[M], st[M], q[M], hh = 0, tt = 1;
int h[M], e[M], ne[M], w[M], idx;
int n, a, b, c;
int spfa()
{
memset(dist, 0xcf, sizeof dist);
q[0] = dist[0] = 0, st[0] = true;
while (hh != tt)
{
int t = q[hh ++ ];
st[t] = 0;
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];
if (!st[j])
{
q[tt ++ ] = j, st[j] = 1;
if (tt == N) tt = 0;
}
}
}
}
return dist[50001];
}
void add(int a, int b, int c)
{
e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++ ;
}
int main()
{
scanf("%d", &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 ++ )
{
scanf("%d%d%d", &a, &b, &c);
add(a, b + 1, c);
}
printf("%d\n", spfa());
return 0;
}