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

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ1023][SHOI2008]cactus仙人掌图  

2014-08-18 20:59:05|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
BZOJ维护一周QAQ

我又要颓一周了。。。

高三大哥STH某天给我们作为测试题第三道

在考场上想把环缩起来之后做树上DP

结果研究了一天发现缩环不可写。。

于是只好学习标解QAQ

第一次写仙人掌DP

比想象中的简单~

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<deque>
using namespace std;
int n,m;
int scan(){
char cc=' ';int re=0,fh=1;
while(cc==' '||cc=='\r'||cc=='\n')cc=getchar();
if(cc=='+'){fh=1;cc=getchar();}
if(cc=='-'){fh=-1;cc=getchar();}
while('0'<=cc&&cc<='9'){
re=re*10+cc-'0';
cc=getchar();
}
return re*fh;
}
const int N = 100000+10;
struct Point{
Point(){next=NULL;}
int d;
Point *next;
void push(int a){
Point *l=new Point;
l->next=next;next=l;
l->d=a;
}
}point[N];
int dfn[N],low[N],T,list[N*2],maxdeep[N][2],deep[N],ans;
int fa[N];
short v[N];
int min(int a,int b){if (a<b)return a;return b;}

deque <int> dui;
int circle(){
int i,j=0,l=0;
for(i=1;i<=list[0]*2;i++){
while(!dui.empty()&&i-dui.front()>list[0]/2) dui.pop_front();

if(!dui.empty())j=dui.front();
if(j)l=max(l,maxdeep[list[j]][0]+maxdeep[list[i]][0]+(i-j)-deep[list[i]]-deep[list[j]]);

if(!dui.empty())j=dui.back();
while((!dui.empty())&&(maxdeep[list[j]][0] + i-j - deep[list[j]] <= maxdeep[list[i]][0] - deep[list[i]])){
dui.pop_back();
j=dui.back();
}
dui.push_back(i);
}ans=max(l,ans);
while(!dui.empty())dui.pop_front();
}
void update(int x,int val){
if(val>maxdeep[x][0]){
maxdeep[x][1]=maxdeep[x][0];
maxdeep[x][0]=val;
}else if(val > maxdeep[x][1]) maxdeep[x][1]=val;
}
void tarjan(int x){
int a,b;
low[x]=dfn[x]=++dfn[0];
maxdeep[x][0]=maxdeep[x][1]=deep[x];
for(Point *i=point[x].next;i!=NULL;i=i->next)
if(!dfn[i->d]){
deep[i->d]=deep[x]+1;fa[i->d]=x;
tarjan(i->d);
low[x]=min(low[x],low[i->d]);
}else if(i->d!=fa[x])
low[x]=min(low[x],dfn[i->d]);
//update ans
for(Point *i = point[x].next;i!=NULL;i=i->next)
if(low[i->d] > dfn[x] && !v[i->d]){//树边
v[i->d]=1;
update(x,maxdeep[i->d][0]);
}else if(deep[i->d]-deep[x]>1 && dfn[i->d] > dfn[x]){//环
a=i->d;list[0]=0;
while(a!=x){
list[++list[0]]=a;
a=fa[a];
}list[++list[0]]=a;
for(int j=1;j<=list[0];j++)
list[list[0]+j]=list[j];
circle();a=0;
for(int j=1;j<list[0];j++)
a=max(a,deep[x]-deep[list[j]]+min(list[0]-j,j)+maxdeep[list[j]][0]);
update(x,a);
}
ans=max(ans,maxdeep[x][0]+maxdeep[x][1]-deep[x]*2);
}
int main(){
//freopen("input.txt","r",stdin);
int i,j,a,b,c;
n=scan();m=scan();
for(i=1;i<=m;i++){
a=scan();
for(j=1;j<=a;j++){
b=scan();
if(j>1){
point[b].push(c);
point[c].push(b);
}c=b;
}
}deep[1]=1;
tarjan(1);
printf("%d\n",ans);
return 0;
}

大致思路就是对于每一个点

先做一边求割边的tarjan

然后扫描每条边

如果是割边就做树上DP

如果是环,而且当前节点是环上deep最小的点

那么环上的其它点就已经都更新完毕了

把这个环提出来用单调队列做DP更新答案


------------------------

之前单调队列部分写挂了QAQ

正确姿势是:

    把超过长度的队首元素出队

    用当前i更新答案

    队尾出队保持单调性

    i入队

但是数据太弱没有测出来(BZOJ上A了)

后来去下了一个50组的数据WA了一片。。

-------------------------------

好不容易过了50组的数据

结果BZOJ上又WA了

检查了一下是局部变量没有赋初值

但是为啥我的电脑这么神全都赋初值0了= =..

  评论这张
 
阅读(18)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

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