<题目链接>
题目大意：
给你$n$段区间，$a_i,b_i,c_i$ 表示在 $[a_i,b_i]$ 区间内至少要选择$c_i$个点。现在问你在满足这n个条件的情况下，最少要选多少个点？
解题分析：
经典的差分约束。本问题需要满足的不等式有：$s[b[i]]-s[a[i]-1]geq c[i]，0leq 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+7; int n,st,ed,cnt; int head[N],dis[N]; bool vis[N]; struct Edge{ int to,val,nxt; Edge(int _to=0,int _val=0,int _nxt=0):to(_to),val(_val),nxt(_nxt){} }edge[N<<2]; 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]=0; 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,-1,sizeof(head)); st=1e9,ed=-1; for(int i=1;i<=n;i++){ int a,b,c;scanf("%d%d%d",&a,&b,&c); add(a-1,b,c); //s[b]-s[a-1]>=c st=min(st,a-1);ed=max(ed,b); } for(int i=st;i<=ed;i++){ //根据添加的两个约束条件建边 add(i-1,i,0); //s[i]-s[i-1]>=0 add(i,i-1,-1); //s[i]-s[i-1]<=1 即 s[i-1]-s[i]>=-1 } spfa(); //因为是">="，与最长路的松弛方式(三角形不等式)相同 printf("%d ",dis[ed]); }