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;
}
本文出自MayFlyyh's Blog,转载时请注明出处及相应链接。
本文永久链接: http://www.mayflyyh.com/archives/305