题意：有n个区间[a,b]，每个区间有一个值c。找一个集合中的元素使得每个区间至少有c个元素在这个集合中，问最小的集合大小。
思路：设d[i+1]表示0到i有多少个数在这个集合中，显然对于每个区间，d[b+1]-d[a]>=c，才能符合题目的要求。但是这样并不能使得所有集合都联系起来。继续挖掘条件，根据d[]的定义可得，0<=d[i+1]-d[i]<=1。
由此可得三个不等式：
d[b+1]-d[a]>=c
d[i+1]-d[i]>=0
d[i]-d[i+1]>=-1
很明显这是一个差分约束系统，只不过求得是最长路。建好图后找到最小值到最大值的最长路就是答案。
#include<stdio.h>
#include<string.h>
const int N=+,M=,INF=0x3f3f3f3f;
struct node{
int v,w,next;
}e[M];
int head[N],p[N],d[N];
int q[M<<],l,r,js;
void add(int u,int v,int w)
{
e[js].v=v,e[js].w=w;
e[js].next=head[u],head[u]=js++;
}
void spfa(int s,int t)
{
l=r=;int u,v,w,i;
for(i=s;i<=t;i++) d[i]=-INF;
memset(p,,sizeof(p));
q[++r]=s;d[s]=;
while(l<r)
{
p[u=q[++l]]=;
for(i=head[u];i!=-;i=e[i].next)
{
v=e[i].v,w=e[i].w;
if(d[v]<d[u]+w)
{
d[v]=d[u]+w;
if(!p[v])
{
p[v]=;
q[++r]=v;
}
}
}
}
printf("%d\n",d[t]);
}
int main()
{
int n,u,v,w,i,ma,mi;
while(scanf("%d",&n)!=EOF)
{
memset(head,-,sizeof(head));
js=ma=;mi=INF;
while(n--)
{
scanf("%d%d%d",&u,&v,&w);
add(u,v+,w);
if(u<mi) mi=u;
if(v+>ma) ma=v+;
}
for(i=mi;i<ma;i++)
{
add(i,i+,);
add(i+,i,-);
}
spfa(mi,ma);
}
return ;
}