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

vfleaking的博客

My name is VFlea King

 
 
 

日志

 
 

2525: [Poi2011]Dynamite  

2013-03-08 13:40:22|  分类: 衡阳八中 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
【题目大意】
Byteotian Cave的结构是一棵n个节点的树,其中某些点上面已经安置了炸药,现在需要点燃m个点上的引线引爆所有的炸药。
某个点上的引线被点燃后的1单位时间内,在树上和它相邻的点的引线会被点燃。如果一个有炸药的点的引信被点燃,那么这个点上的炸药会爆炸。
求引爆所有炸药的最短时间。

1<=M<=N<=300000


>_<
最烦这种题目了……太恶心了……
什么树上的所有点和重要点的距离和要算进代价啊,升级重要点是有一些限制的啊,问代价最小是多少啊……(1162: [CTSC2004]网络改造)
什么树上有一些神奇的点,它能管理最多s个点啊,且与它的距离不超过k啊,问至少要设立几个神奇的点啊……(1117: [POI2009]救火站Gas)

看到这道题后我眼前一片漆黑……
使劲想了会儿也不会做……
果断去看波兰人写的题解……
好了这篇日志转述下波兰人的题解内容……

【Wprowadzenie】(介绍)
想到的一般都是非多项式算法对吧好难过……
我们来把这个问题转化为判定性问题,枚举 t,t是总用时,我们现在的任务是判断只用t时间是否可行。
Problem decyzyjny dla ustalonego t】(对于一个给定的t进行判定)
以某个结点为根建成一棵树不必再说了吧……
定义:(Name and Conquer)
N(v):说从前我们设一个集合N(v),代表与v结点的距离不超过t的所有结点组成的集合。即 {u | dist(v, u) <= t} dist代表两点之间的距离。
酱油结点:那么如果说现在有个结点v,它有个父亲fa,N(v)是N(fa)的子集……那么v结点显然没必要点火对吧。我们把这样的结点叫做酱油结点。
t阶父亲:1阶父亲就是父亲,2阶父亲是父亲的父亲,3阶父亲是父亲的父亲的父亲……明白了吧……

好~那么现在可以给出暴力算法:

procedure check(t)
begin
while 树不为空 do begin
if 有一个没有放炸药的叶子 then
把这个叶子删了.... // 因为首先没放炸药说明不必被点燃,其次这个叶子点火了的话还不如把它父亲点着
else if m = 0 then // m记录的是剩余还可以点几次火
return No;
else begin
h = 树的高度;
if h <= t then // 可以直接把树根给点着了
return Yes;
v = 树中深度最深的结点;
m = m - 1;
把v的t阶父亲给点了;
end
end
return Yes;
end

核心部分是把最深的结点的t阶父亲给点了……这是为什么呢……
首先由于v是最深的结点,那么v的t阶父亲的所有子孙都肯定是酱油结点了吧。那么肯定不能把子孙给点着了。
那么如果不点t阶父亲的话,肯定也没人能把v给点着了。
所以一定要点t阶父亲。
(刹那间t阶父亲化为火球……)

所以上面的伪代码是正确的。但时间复杂度极高。

Przyspieszamy algorytm】(加速算法)
1.Ograniczamy liczb sprawdzeń(限制检查次数)
真是汗啊……波兰人之前说的居然是枚举t……其实二分t就行了……不再赘述
2.Przyspieszamy sprawdzenie(加快检查)
之前的是正确方法但是不利于实现……
(其实我觉得也是可以的啊,先bfs求出父亲和深度,然后用优先队列维护最深的结点,每次取出来最深的结点再乱搞下。由于最深深度是上升的,而且是[1, n]的,所以可以直接用桶来实现优先队列。这样check一次的总时间复杂度就是O(n))
现在考虑一种类似dp的实现。跟之前的那种算法本质是一样的。做的是完全相同的事情。

如果一个结点v在某个已经点着了的结点的影响范围之内,那么显然不用考虑v了。所以要记录:
fire[v]:表示离v最近的被点着的结点与v之间的距离。(你要不要说话这么绕人……)
我们只关心最近的。

之前算法中,如果一个结点v有一个深度最深的后裔,且之间的距离等于t的话,就要点着它。
而深度最深的后裔实际上是子树中没被点着的携带火药的最深的结点。(回忆之前的算法~)
所以再记录:
dynamite[v]:表示离v最远的没被点着的携带火药的结点与v之间的距离。(你要不要说话这么绕人……)
我们只关心最远的。

那么如何玩这两个数组呢……(那个长得像横着的糖葫芦的是负无穷大……)

procedure handle(v)
begin
// 显然
fire[v] = ∞;
dynamite[v] = -∞;
if v上面有火药 then
dynamite[v] = 0;

// 显然
foreach v的每个儿子w do begin
dynamite[v] = max(dynamite[v], dynamite[w] + 1);
fire[v] = min(fire[v], fire[w] + 1);
end

if dynamite[v] + fire[v] <= t then
dynamite[v] = -∞;

// 显然
if dynamite[v] = t or (v是根 and dynamite[v] != -∞) then begin
m = m - 1;
dynamite[v] = -∞;
fire[v] = 0;
end
end

就是个之前的那份伪代码的变形而已……
唯一不显然的地方就是

if dynamite[v] + fire[v] <= t then
dynamite[v] = -∞;

这是为啥呢囧……
首先对于一个结点v一定不会有dynamite[v] + fire[v] <= t
不然那个火药就会被这个着火的地方给点了。(回忆之前的伪代码)
那么我们此时出现了这种情况,说明搞出来的这个火药和着火点一定来自不同的子树。
可以用着火点绕过长长的山路,把火药给点了。
由于最远的火药都被点了,更近一点的火药有什么话说?一定也被点了嘛。
所以子树中所有火药都被点了。

这样是O(nlogn)的满分算法。

然后我就A掉了。这种题好难想啊……哭烂了……
  评论这张
 
阅读(1069)| 评论(5)
推荐 转载

历史上的今天

评论

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

页脚

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