POJ 1201 Intervals

题意：给m个区间li,ri,再给一个ci，要求在每个区间li-ri种至少选ci个数，求满足条件最小选的数字。
数字值域：0~50000，m<=50000

哎，考虑差分约束，设D[i]表示从0-i满足条件至少选多少个

l-r，至少选C个，即D[r]-D[l-1]>=c，从l-1到r连一条权值为c的边

然后隐藏条件:0<=D[i]-D[i-1]<=1

然后呢？选一个最小的li，跑向最大的ri。

注意一下数组下标

CODE:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<string>
const int N = 101010;
int n,s=0x3f3f3f3f,t;
int dis[N],l[N],r[N],cnt,v[N],last[N],c[N];
inline int read(){
    int x=0,flag=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')flag*=-1;c=getchar();}
    while(isdigit(c)){x=(x<<3)+(x<<1)+c-'0';c=getchar();}
    return x*flag;
}
struct egde{
    int next,to,v;
}e[320000];
inline int add(int a,int b,int c){
    cnt++;a++,b++;
    if(a<0||b<0) printf("!1");
    e[cnt].next=last[a],last[a]=cnt;
    e[cnt].to=b,e[cnt].v=c;
    return 0;
}
inline int spfa(){
    std::queue<int> q;
    while(!q.empty()) q.pop();
    q.push(s);
    memset(dis,-0x3f,sizeof(dis));
    dis[s]=0;
    while(!q.empty()){
        int x=q.front();v[x]=0;q.pop();
        for(int i=last[x];i;i=e[i].next){
            if(dis[e[i].to]<dis[x]+e[i].v){
                dis[e[i].to]=dis[x]+e[i].v;
                if(!v[e[i].to]){
                    v[e[i].to]=1;
                    q.push(e[i].to);
                }
            }
        }
    }
    return dis[t];
}
int main(){
    n=read();
    for(int i=1;i<=n;++i){
        l[i]=read(),r[i]=read(),c[i]=read();
        add(l[i]-1,r[i],c[i]);
        s=std::min(l[i],s);
        t=std::max(r[i]+1,t);
        /*

            D[r]-D[l-1] >= c
            D[r]-c>=D[l-1];
            D[l-1]+c<=D[r];

            a[l]-a[l-1]<=1;
            a[l]-1<=a[l-1];
            a[l]-a[l-1]>=0;
            a[l-1]<=a[l];
        */
    }
    for(int i=0;i<=t;++i){
        add(i,i-1,-1);
        add(i-1,i,0);
    }
    int ans=spfa();
    printf("%d\n",ans);
    return 0;
}