第二十届全国信息学奥林匹克竞赛（2003）第二试

兔子

题1

---

逃学的小孩
【问题描述】
Chris 家的电话铃响起了，里面传出了Chris的老师焦急的声音：“喂，是Chris的家长吗？你们的孩子又没来上课，不想参加考试了吗？”一听说要考试，Chris的父母就心急如焚，他们决定在尽量短的时间内找到Chris。他们告诉Chris的老
师：“根据以往的经验，Chris现在必然躲在朋友Shermie 或Yashiro 家里偷玩《拳皇》游戏。现在，我们就从家出发去找Chris，一但找到，我们立刻给您打电话。”说完砰的一声把电话挂了。
Chris 居住的城市由N 个居住点和若干条连接居住点的双向街道组成，经过街道x需花费Tx分钟。可以保证，任两个居住点间有且仅有一条通路。Chris家在点C，Shermie 和Yashiro 分别住在点A 和点B。Chris的老师和Chris的父母都有城市地图，但Chris的父母知道点A、B、C的具体位置而Chris的老师不知。

为了尽快找到Chris，Chris 的父母会遵守以下两条规则：
l 如果A 距离C 比B 距离C 近，那么Chris 的父母先去Shermie 家寻找Chris，如果找不到，Chris的父母再去Yashiro 家；反之亦然。
l Chris 的父母总沿着两点间唯一的通路行走。

显然，Chris 的老师知道Chris 的父母在寻找Chris的过程中会遵守以上两条规则，但由于他并不知道A，B，C 的具体位置，所以现在他希望你告诉他，最坏情况下Chris的父母要耗费多长时间才能找到Chris？

（见附件）
例如上图，这座城市由4个居住点和3条街道组成，经过每条街道均需花费1分钟时间。假设Chris住在点C，Shermie 住在点A，Yashiro 住在点B，因为C到B的距离小于C到A的距离，所以Chiris的父母会先去Yashiro 家寻找Chris，一旦找不到，再去Shermie 家寻找。这样，最坏情况下Chris 的父母需要花费4分钟的时间才能找到Chris。

【输入文件】
输入文件hookey.in第一行是两个整数N（3 £ N £ 200000）和M，分别表示居住点总数和街道总数。以下M 行，每行给出一条街道的信息。第i+1 行包含整数Ui、Vi、Ti（1£Ui, Vi £ N，1 £ Ti £ 1000000000），表示街道i连接居住点Ui
和Vi，并且经过街道i需花费Ti分钟。街道信息不会重复给出。

【输出文件】
输出文件hookey.out 仅包含整数T，即最坏情况下Chris 的父母需要花费T分钟才能找到Chris。

【样例输入】
4 3
1 2 1
2 3 1
3 4 1
【样例输出】
4


题2

---

草莓
【题目背景】
尽管不少人都吃过鲜美的草莓，却很少有人真正的看过野草莓的成长。它们从自己的枝上伸出一根根长长的触须，每当遇到合适的地方就会扎根发芽，生长出来一株新的草莓。所以，当你在森林中遇到一株草莓的时候，通常就意味着你
会在它的周围找到一片草莓田。但这些草莓并非可以永远做无忧无虑的精灵，树林中穿梭的鸟儿和偶尔路过的鹿群都喜欢吃这种美味的浆果。不过，他们最大的威胁却是来自那些酷爱草莓的棕熊。他们不但可以吃掉整整一片草莓，而且还会粗鲁地把一片草莓田搞得乱七八糟。于是每当一块草莓田越长越大之后，森林中的精灵们就会把一块草莓田分开来种到空地中去，以免被粗鲁的棕熊搞乱。不过这些好心的精灵并不希望把草莓分得太散，因为草莓们会感到孤单。所以她们希望按照空地的数目来分割草莓田，使得每块空地上恰好可以放上一块用触须连接在一起的草莓田，且使得所有空地上含有草莓浆果的最小重量最大。可是天真的精灵并不知道怎么来做这件事情，你可以帮助他们吗？
（此处有一张草莓图==！！见附件）

【任务描述】
你的任务就是要把一片草莓田分割成k块从而转移到k块空地上，而你的这个分割方案需要满足如下的条件：
l 每一块中的草莓必然是直接或者间接通过触须和其他草莓相连接的；l 这种分割方案所对应的每块空地上草莓重量之和的最小值在所有分割方案中最大；
最后输出你的分割方案和结果。
值得注意的是，虽然按道理来说草莓间互相连接的触须应该符合某些特定的关系，形成一些规则的图案。但在富饶的森林中，长势良好的草莓经常会把触须缠绕在一起。这个时候，精灵们会认为这其实是一根触须。所以精灵们给你的草
莓田可能会形成复杂的图案。甚至由于鸟儿或者鹿群的捣乱，一块草莓田中的有些草莓甚至没有通过触须和其他的草莓连接在一起。不过这并不影响最后的结果，你只要把一块草莓田分割成为k 块通过触须连接在一起的小草莓田就可以了。

【输入说明】
第一行为三个整数n、m 及k，n 表示草莓的株数，m 表示草莓间伸出的触须的数目，k为空地的数目。
接下来的n 行每行两个整数i 及bi，表示第i 株草莓上面结了bi克的草莓。
顺序下来的m行每行两个整数p和q，表示p、q之间有触须相连接。
另外，在所有这些数据的最后还有单独的一行包括一个整数d用作评分，有关d的说明，可以参看下面的评分方法。
【输出说明】
你一共要输出k+1行。第一行为一个整数x，表示你分割的草莓田中最大的最小重量。然后下面的n行中，每行第一个整数为ni，表示按照这个重量分割出来的第i块草莓田中含有多少株草莓。然后该行中接下来的ni个整数为这些草莓
的编号。请注意一行中草莓必然是通过触须相连接的。
【输入样例】
7 9 3
1 4
2 4
3 3
4 1
5 5
6 7
7 2
1 2
1 6
2 3
2 5
2 6
4 5
4 6
6 7
2000000000
【输出样例】
7
2 1 6
2 2 3
3 4 5 7

（图见附件）

【评分方法】
你的需要针对berry1.in~berry10.in 这10 个给定的输入文件给出你的输出berry1.out~berry10.out 并放在你的选手目录下。我们将根据你给出的输出文件给出分数。对于某一确定的测试点来说，如果你的输出文件中第一行的x和下面的分割方案不符合，或者是输出文件本身就有错误，那么你将得不到该测试点的分数。这里输出文件的错误可以使用我们提供的berry_check 检查工具进行检查。
只有当这个程序输出Yes的时候，你的输出才可以确认是可接受的。
可接受的输出将被我们进一步的计算来获得你最后的分数。如果我们记你输出文件中的最大的最小重量为x，而我们的最优结果为best，则我们根据如下的公式计算你的分数：
（图见附件）
这里的d为上面输入数据中最后一行输入的整数。

【你如何测试自己的输出】
我们提供berry_check 这个工具作为测试你的输出文件的办法。使用这个工具的方法是：
berry_check <输入文件名> <输出文件名>
在你调用这个文件后，berry_check 将根据你给出的输入和输出文件给出测试的结果，其中包括：
l 非法退出：该点得0分；
l not connect：你程序输出的行中含有不连通的分量；
l duplicate：同一点输出了两次；
l extra：输出文件中包括多余数据；
l lack：输出的总点数不对；
l answer not match：输出中第一行的结果和实际结果不符；
l Yes：输出正确，将进行下一步的评分。


题3

---

智破连环阵
【问题描述】
B国在耗资百亿元之后终于研究出了新式武器——连环阵（Zenith Protected Linked Hybrid Zone）。传说中，连环阵是一种永不停滞的自发性智能武器。但经过A国间谍的侦察发现，连环阵其实是由M 个编号为1，2，…，M的独立武器组成的。最初，1号武器发挥着攻击作用，其他武器都处在无敌自卫状态。以后，一旦第i（1 £ i< M）号武器被消灭，1秒种以后第i+1号武器就自动从无敌自卫状态变成攻击状态。当第M 号武器被消灭以后，这个造价昂贵的连环阵就被摧
毁了。
为了彻底打击B 国科学家，A 国军事部长打算用最廉价的武器——炸弹来消灭连环阵。经过长时间的精密探测，A 国科学家们掌握了连环阵中M 个武器的平面坐标，然后确定了n个炸弹的平面坐标并且安放了炸弹。每个炸弹持续爆炸时间为5分钟。在引爆时间内，每枚炸弹都可以在瞬间消灭离它平面距离不超过k 的、处在攻击状态的B 国武器。和连环阵类似，最初a1号炸弹持续引爆5分钟时间，然后a2号炸弹持续引爆5 分钟时间，接着a3号炸弹引爆……以此类推，直到连环阵被摧毁。
显然，不同的序列a1、a2、a3...消灭连环阵的效果也不同。好的序列可以在仅使用较少炸弹的情况下就将连环阵摧毁；坏的序列可能在使用完所有炸弹后仍无法将连环阵摧毁。现在，请你决定一个最优序列a1、a2、a3…使得在第ax号炸
弹引爆的时间内连环阵被摧毁。这里的x应当尽量小。

【输入文件】
输入文件zplhz.in第一行包含三个整数：M、n 和k（1≤M, n≤100，1≤k≤1000），分别表示B国连环阵由M个武器组成，A国有n个炸弹可以使用，炸弹攻击范围为k。以下M行，每行由一对整数xi，yi（0≤xi，yi ≤10000）组成，表示第i（1≤i≤M）号武器的平面坐标。再接下来n行，每行由一对整数ui，vi(0≤ui，vi≤10000)组成，表示第i（1≤i≤n）号炸弹的平面坐标。输入数据保证随机、无误、并且必然有解。

【输出文件】
输出文件zplhz.out 的第一行包含一个整数x，表示实际使用的炸弹数。第二行包括x 个整数，依次表示a1，a2，…，ax。

【样例输入1】
4 3 6
0 6
6 6
6 0
0 0
1 5
0 3
1 1
0 0
【样例输出1】
2
1 3

【样例输入2】
10 10 45
41 67
34 0
69 24
78 58
62 64
5 45
81 27
61 91
95 42
27 36
91 4
2 53
92 82
21 16
18 95
47 26
71 38
69 12
67 99
35 94
【样例输出2】
5
6 2 1 3 4

【评分标准】
如果你的输出不合法，则只能得0分。否则设已知最优解为best，你的答案为ans，则你的得分取决于二者之差ans-best：
（图见附件）
注意如果按照上面的计算方法，你在一个测试点中的得分可能超过10。但如果你在这道题目中的得分如果计算出来大于100分，我们将会按照100分来算。所以该道题目的最大的分还是100分。