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

z55250825

一只蒟蒻

 
 
 

日志

 
 

【BZOJ1304】【Cqoi2009】【叶子的染色】  

2014-04-11 23:38:22|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
   题目大意:给出一棵树,然后每个节点有三种状态,无色,黑色,白色,然后可以选取一个点作为根,然后给叶子节点染色,要求保证每一个叶子节点到根的路径上都有点被染色。再给出每一个叶子节点到根路径上的最早的一个有色节点的颜色(这点bzoj的描述差评T^T)(其实应该是原来的题目描述差评!),求染色最少的节点并能满足上面两个条件。

   这题神题不会= =...感觉DFS,DP,图论,网络流什么的都貌似聊不上233...然后是看题解的....

   这题需要一个结论,这个结论貌似还是无人证明的节奏??
   结论在这里恩0.0 戳结论
   结论大意就是,无论选哪个非叶子节点做根,最后的答案都是一样的。
   链接的空间的下面的评论中貌似有一个证明了恩......
   证明的正确性待会儿再想吧。

   考虑随便选一个点之后,咱们需要做的就是满足一堆节点的要求即可。那么咱们从题解发现可以进行树形dp了。然后咱们来考虑状态...

    然后突然发现题目又读错了,其实只有 叶子节点的 才有c[]233...
    关于dp的具体思路可以看重来君的 dp方程   
    这题知道了开头那个结论了就还是比较水的,不知道对咱这种蒟蒻还真是一道神题的感觉唔 = =

    注意叶子直接处理即可,注意要及时退出!!
===============================

program bzoj1304;
const maxn=10010;
type edge=record
v,pre:longint;
end;

var e:array[0..maxn*2]of edge;
fa,c,last:array[0..maxn]of longint;
f:array[0..maxn,0..2]of longint;
n,m,tot:longint;

function min(a,b:longint):longint;
begin
if a<b then exit(a) else exit(b);
end;

procedure addedge(u,v:longint);
begin
inc(tot);e[tot].v:=v;
e[tot].pre:=last[u];last[u]:=tot;
inc(tot);e[tot].v:=u;
e[tot].pre:=last[v];last[v]:=tot;
end;

procedure dfs(p:longint);
var tmp,sum1,sum2,sum3:longint;
begin
tmp:=last[p];
if p<=n then
begin
f[p][0]:=1;
f[p][c[p]+1]:=0;
f[p][2-c[p]]:=1;
exit;
end;
sum1:=0;sum2:=0;sum3:=0;
while tmp<>0 do
begin
if fa[p]<>e[tmp].v then
begin
fa[e[tmp].v]:=p;
dfs(e[tmp].v);
sum1:=sum1+f[e[tmp].v][0];
sum2:=sum2+min(f[e[tmp].v][0],f[e[tmp].v][1]);
sum3:=sum3+min(f[e[tmp].v][0],f[e[tmp].v][2]);
end;
tmp:=e[tmp].pre;
end;
f[p][0]:=min(sum1,min(sum2,sum3)+1);
f[p][1]:=min(sum2,sum3+1);
f[p][2]:=min(sum3,sum2+1);
end;

procedure init;
var i,u,v:longint;
begin
read(m,n);
for i:=1 to n do read(c[i]);
fillchar(last,sizeof(last),0);
tot:=0;
for i:=1 to m-1 do
begin
read(u,v);
addedge(u,v);
end;
fillchar(fa,sizeof(fa),0);
fillchar(f,sizeof(f),0);
dfs(m);
write(f[m][0]);
end;

begin
init;
end.


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

历史上的今天

评论

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

页脚

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