POJ 1201 Intervals

作者: MayFlyyh 分类: 最短路 发布时间: 2018-08-11 16:22 ė 6 没有评论

题意:给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;
}

本文出自MayFlyyh's Blog,转载时请注明出处及相应链接。

本文永久链接: http://www.mayflyyh.com/archives/305

发表评论

电子邮件地址不会被公开。

Captcha Code

Ɣ回顶部