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

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ1040][ZJOI2008]骑士  

2014-09-01 22:06:50|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

1040: [ZJOI2008]骑士

写了1.5节课,DEBUG了1.5节课
忽略了好多细节导致各种WA
TAT我不应该轻信GTY的话去开什么开学大会
现在一大坨作业没写我要死了(╯‵□′)╯︵┻━┻

//BZOJ 1040 KNIGHT ZJOI2008
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1e6+100;
int n,m;
int scan(){
char cc=' ';int re=0,fh=1;
while(cc==' '||cc=='\r'||cc=='\n')cc=getchar();
if(cc=='+')cc=getchar(),fh=1;
if(cc=='-')cc=getchar(),fh=-1;
while('0'<=cc&&cc<='9'){
re=re*10+cc-'0';
cc=getchar();
}return re*fh;
}
struct Point{
Point(){next= NULL;}
Point *next;int d;
void push(int a){
Point *l = new Point;
l->d = a;
l->next = next;next = l;
}
}point[N];
typedef long long LL;
LL f[N][2],w[N],ans,lf[N][2];
int dfn[N],fa[N],low[N],deep[N];
int list[N*2];
void circle(int x){
int l =0;
memset(lf,0,sizeof(lf));
for(int i=1;i<list[0];i++){
lf[i][0] = max(lf[i-1][0],lf[i-1][1]) + f[list[i]][0];
lf[i][1] = lf[i-1][0] + max(f[list[i]][0],f[list[i]][1]);
}
f[x][0] += max(lf[list[0]-1][0],lf[list[0]-1][1]);
memset(lf,0,sizeof(lf));
//强制不选第一个,可以update f[x][1]
lf[1][1] = 0;
lf[1][0] = f[list[1]][0];
for(int i=2;i<list[0];i++){
lf[i][0] = max(lf[i-1][0],lf[i-1][1]) + f[list[i]][0];
lf[i][1] = lf[i-1][0] + max(f[list[i]][0],f[list[i]][1]);
}
f[x][1] += lf[list[0]-1][0];
}
short v[N];
void dfs(int x){
low[x] = dfn[x] = ++dfn[0];
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;
dfs(i->d);
low[x] = min(low[x],low[i->d]);
}else if(fa[x]!=i->d){
low[x] = min(low[x],dfn[i->d]);
}
f[x][1] = w[x];
for(Point *i = point[x].next;i!=NULL;i=i->next)
if(low[i->d] > dfn[x] && !v[i->d]){//树边
v[i->d]=1;//处理重边
f[x][0] += max(f[i->d][0],f[i->d][1]);
f[x][1] += f[i->d][0];
}else if(deep[i->d] - deep[x] > 1 && dfn[i->d] > dfn[x]){//环
int a = i->d;
list[0]=0;
while(a!=x){
list[++list[0]] = a;
a=fa[a];
}list[++list[0]] = x;
circle(x);
}
}
int main(){
int i,j;
n=scan();
for(i=1;i<=n;i++){
w[i] = scan();
j=scan();
point[i].push(j);
point[j].push(i);
}
for(i=1;i<=n;i++)
if(!dfn[i]){//多个联通块
dfn[0]=0;
deep[i]=1;
dfs(i);
ans += max(f[i][0],f[i][1]);
}
printf("%lld\n",ans);
return 0;
}

题解:
环+外向树DP
要注意的细节是
1.有可能会分成多个联通块
2.重边
  评论这张
 
阅读(345)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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