【题目链接】 

 

【题目大意】 

　　告诉你一个区间至少要选定的数字的个数，给出n个区间的需求

　　问最少选取几个数字可以满足所有的需求

 

【题解】

　　对于区间[a,b]建立不等式S_b+1-S_a>=c，最后要求最小化Smax，

　　结合基础条件S_i+1-S_i>=0,S_i-S_i+1>=-1，构造差分约束系统求最长路就是答案。

 

【代码】

#include 
     
      #include 
      
       #include 
       
        using namespace std;const int N=200010,inf=~0U>>2,M=200000;int time[N],q[N],size,h,t,n,ed,dis[N],in[N],nxt[N],w[N],v[N],g[N],ma,mi,u,e,cost;void add(int x,int y,int z){v[++ed]=y;w[ed]=z;nxt[ed]=g[x];g[x]=ed;}int spfa(int S){    for(int i=0;i<=n;i++)dis[i]=-inf,in[i]=0,time[i]=0;    time[S]=1,dis[S]=0,in[S]=1;    int i,x,size; q[h=t=size=1]=S;    while(size){        for(i=g[x=q[h]],h=(h+1)%M,size--;i!=-1;i=nxt[i])if(dis[x]+w[i]>dis[v[i]]){            dis[v[i]]=dis[x]+w[i];            if(!in[v[i]]){                time[v[i]]++,t=(t+1)%M,size++,in[q[t]=v[i]]=1;                if(time[v[i]]>n)return -1;            }        }in[x]=0;    }if(dis[n]==-inf)return -2;    return dis[n];}int main(){    while(~scanf("%d",&n)){        ed=0;memset(g,-1,sizeof(g));        ma=-inf; mi=inf;        for(int i=1;i<=n;i++){            scanf("%d%d%d",&u,&e,&cost);            add(u,e+1,cost);            ma=max(e+1,ma); mi=min(u,mi);        }for(int i=mi;i