注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

那一日,泪水打湿雪花冰冷的心

曾经的滋味,回忆在一次次的离合中,回眸时,那一刻,如涟漪般在一刹那融化

 
 
 

日志

 
 

POJ 1201  

2010-06-15 21:44:56|  分类: poj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
问题是说,给定若干个区间,从区间中选点,使得每个区间选的点数满足一个下限,然后求满足要求的最少的点数
这个题可以用差分约束系统来解决,设s[x]为1到x之间选的点的个数,那么s[bi]-s[ai-1]>=ci,且有0=<s[x+1]-s[x]<=1
因为求满足要求的最小值,所以要求最长路,同理差分约束系统中如果求满足要求的最大值就是求最短路,相关差分约束系统的内容参看这篇文章http://imlazy.ycool.com/post.1702305.html
#include<cstdio>
#include<cstring>
const int maxm=300001;
const int maxint=-100000000;
int pnt[maxm],cost[maxm],head[maxm],nxt[maxm],n,a1,a2,a3,k,e,d[maxm],list[maxm];
inline void addedge(int s0,int t0,int c0){
pnt[e]=t0;cost[e]=c0;nxt[e]=head[s0];head[s0]=e++;
}
void spfa(int x2){
     int ft=0,tl=1;
     int flag[n+1];
     for(int i=0;i<n;i++){
       d[i]=maxint;
       flag[i]=true;
     }
     if(n==0||n==1)
return;
     list[0]=x2;d[x2]=0;flag[x2]=false;
while(ft!=tl){
       int oldf=list[ft];
       ft=ft<n-1?ft+1:0;
       for(int i=head[oldf];i!=-1;i=nxt[i])
         if(d[oldf]+cost[i]>d[pnt[i]]){
           d[pnt[i]]=d[oldf]+cost[i];
           if(flag[pnt[i]]){
if(d[pnt[i]]>=d[oldf]){
ft=ft?ft-1:n-1;
list[ft]=pnt[i];
}else{ 
list[tl]=pnt[i];
tl=tl<n-1?tl+1:0;
}
flag[pnt[i]]=false;
}
         }
flag[oldf]=true;
     }
}
int main(){
memset(nxt,-1,sizeof(nxt));
memset(head,-1,sizeof(head));
scanf("%d",&n);
int mm=0,ma=100000;
for(int i=0;i<n;i++){
scanf("%d%d%d",&a1,&a2,&a3);
if(a1>a2){
a1=a1+a2;
a2=a1-a2;
a1=a1-a2;
}
addedge(a2+1,a1,a3);
if(a2+1>mm)
mm=a2+1;
if(a1<ma)
ma=a1;
}
n=50004;
for(int i=ma;i<=mm;i++){
addedge(i+1,i,0);
addedge(i,i+1,-1);
// addedge(n-1,i,0);
}
// addedge(n-1,mm+1,0);
spfa(mm+1);
printf("%d\n",d[ma]-d[mm+1]);
return 0;
}
发现不另加结点的会比加结点快很多
  评论这张
 
阅读(1279)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017