<题目链接>
题目大意：
给你$n$段区间，$a_i,b_i,c_i$ 表示在 $[a_i,b_i]$ 区间内至少要选择$c_i$个点。现在问你在满足这n个条件的情况下，最少要选多少个点？
解题分析：
经典的差分约束。本问题需要满足的不等式有：$s[b[i]]-s[a[i]-1]\geq c[i]，0\leq s[i]-s[i-1]\leq 1$，其中s[i]表示到第i个位置为止，所选择的点的个数。
转换一下，就能够得到：
$s[b[i]]\geq s[a[i]-1]+c[i]$
$s[i]\geq s[i-1]+0$
$s[i-1]\geq s[i]+(-1)$ 以上转载于 >>>
差分约束不等式与最短(长)路结合的评价标准就是：如果不等式的约束条件是"<="，比如b-a<=n，就是将其在图中转化为add(a,b,n)，然后跑最短路，因为那个式子能够转化为 b<=a+n ，这与最短路松弛操作中的三角形不等式 (dis[v]<=dis[u]+w，最终目地的三角形不等式)类似，这里的b就相当于v,a相当于u,所以是a--->b连边。
同理，如果是b-a>=n，就是a--->b连边，然后跑最长路，需要注意的是，由于边权在差分约束中很有可能出现负数，所以一般用SPFA求解最短(长)路。
比如本题就是用SPFA求最长路。
#include <bits/stdc++.h>
using namespace std; const int N=5e4+;
int n,st,ed,cnt;
int head[N],dis[N];
bool vis[N];
struct Edge{
int to,val,nxt;
Edge(int _to=,int _val=,int _nxt=):to(_to),val(_val),nxt(_nxt){}
}edge[N<<];
queue<int>q;
inline void add(int u,int v,int w) {
edge[++cnt]=Edge(v,w,head[u]);
head[u]=cnt;
}
void spfa(){ //利用spfa求最长路
memset(dis,-0x3f,sizeof(dis));
q.push(st);
vis[st]=true;dis[st]=;
while(q.size()){
int u=q.front();q.pop();
vis[u]=false;
for(int i=head[u];~i;i=edge[i].nxt){
int v=edge[i].to;
if(dis[v]<dis[u]+edge[i].val){
dis[v]=dis[u]+edge[i].val;
if(!vis[v])q.push(v),vis[v]=true;
}
}
}
}
int main(){
scanf("%d",&n);
memset(head,-,sizeof(head));
st=1e9,ed=-;
for(int i=;i<=n;i++){
int a,b,c;scanf("%d%d%d",&a,&b,&c);
add(a-,b,c); //s[b]-s[a-1]>=c
st=min(st,a-);ed=max(ed,b);
}
for(int i=st;i<=ed;i++){ //根据添加的两个约束条件建边
add(i-,i,); //s[i]-s[i-1]>=0
add(i,i-,-); //s[i]-s[i-1]<=1 即 s[i-1]-s[i]>=-1
}
spfa(); //因为是">="，与最长路的松弛方式(三角形不等式)相同
printf("%d\n",dis[ed]);
}