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

fanhq666的博客

Fan-Fun

 
 
 

日志

 
 

树的重心应用题:宇宙大一统  

2011-09-25 12:13:34|  分类: 程序 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
【问题背景】
随着文明间反常的技术爆发,“黑暗森林”状态正在发生着悄悄的改变。
我们把宇宙简化成为N个星球。一开始,每个星球上孕育了一个文明。
由于星球间的通信是昂贵且危险的,所以只有一种建立通信线路的方式:战争。某些时刻,由A文明控制的星球a和B文明控制的星球b发生了一次战争,导致了A、B文明融合成为一个新的文明,而a和b之间建立了一条双向的通信线路。我们定义同一个文明的两个星球x,y间的通信距离D(x,y)是他们相互连通所需要经过的通信线路的最少个数。
每当两个文明融合成为一个新的文明,这个文明需要给自己确定一个星球作为首都。每个星球a都有一个固有的权值W[a],而在一个文明C在星球c建立首都所要付出的通信代价定义为:属于这个文明的所有的星球到首都的通信距离乘以其星球的权值,即
sum([D(i,c)*W[i] for i in C])
由于首都位置的决定往往会引发激烈的内部政治斗争,所以理智的文明总是事先规定:在通信代价最小的地方建立首都。
随着战争的进行,宇宙终于被一个起源于地球的文明所统治。然而,失去了共同敌人的人类爆发了毁灭性的内战,导致了宇宙局部的一次大爆炸,又一次的轮回开始了。
【问题描述】
你得到了一部宇宙简史。它包含了若干个轮回,每个轮回开始时,宇宙中形成了N个孤立的星球(每个轮回的N是不一定相同的),每个星球上都有一个文明。接下来,发生了N-1次战争,每次是属于两个不同文明的星球间的战争,战争的结果是一条新的通信线路的建立和两个文明的融合。
你很想知道每次文明融合的时候首都都被建立在了哪里。但是,你发现可以建首都的地方可能不止一个。于是,你想知道:每次战争后建立的首都所付出的通信代价是多少?
【输入格式】
为了强迫你使用在线算法,本题使用十分奇特的输入格式。请按照我们提供给你的代码框架进行编程。至少我们认为,不使用这个框架是没有任何好处的。接口规范被定义在拥有详细注释的代码里。如果你确信你理解了这个框架的全部行为,你可以不使用我们提供的框架。一切后果自负。
【输出格式】
代码框架帮助你完成输出。
【评分标准】
本题只有一个输入文件,时间限制10s。你可以选择性的跳过一些轮回以防止超时。重要提示:释放内存和写文件是耗时且带有不确定性因素的工作,请不要把时间卡得太紧。对每个轮回,如果你回答对了所有的通信代价,那么你可以获得相应的分数。
对于所有的数据,1<=W[i]<=100,2<=N<=200000。
下面这个表格给出了各个轮回内的宇宙的规模以及分值。
(表格:略)


这个题目的意义:
1.展示了树的重心的强大威力。
2.论证了在传统题目中如何卡离线算法。

这是一个“成品”题,需要使用动态树+树的重心的知识。
思路嘛,就是使用动态树维护树的重心,利用新的重心在原来重心的连线上这个定理。需要维护的信息比较有技巧性,关键是处理把根翻转过来这个操作。标程、代码框架如下:
如果有好的解题思路,欢迎留言。
另外如果要把此题应用在考试、练习中,可以和我联系以获得更多的有关数据生成、代码框架的细节。
  评论这张
 
阅读(1671)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

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