POJ 1201 Intervals（差分约束）

Intervals
题意：给n个区间，一个集合Z，对于第i个区间[a, b]，集合Z与区间[a,b]的交集元素个数大于等于 $c_i$ci​。已知n个区间以及c，问你集合Z的大小最小是多少？
思路：
特征:最小值、不等式
所以我们尝试差分约束的思想，写不等式

差分约束
差分约束是解决这样一类问题
给出n个形如x[j]−x[i] <= k的式子，求x[n]−x[1]的最大/最小值

观察题目，k与c很类似，那我们想怎样构造不等式呢？
对于一个区间[a, b]，Z与其交集的个数至少为c个
x[b] - x[a - 1] <= c
这不就是前缀和表达式吗？
由于a可能为0，所以a - 1会减成-1
所以，我们在此规定，所有区间[a,b] 转化成 [a + 1, b + 1]
那么x[i]含义为0-i在集合Z出现的次数

除了n个表达式外，还有一个限制条件
$1>=x\left[i\right]-x[i-1]>=0$1>=x[i]−x[i−1]>=0
由于我们要求的是最小值，所以把式子全写成x[j] >= x[i] + k，然后求一个最长路即可

AC代码