全国赛师大附中集训测验

1、1 网络改造(network)【背景描述】HURRICANE 小组原来构建的网络由网络上的交换机及其间的网路。交换机分级连接，的为顶级的网关交换机，其他交换机分级相连到该网关交换机上。但值得注意的是，任一台非网关交换机与一台高一级的交换机直接相连。而任一台交换机均可以与几台低一级的交换机直接相连。但最近，由于原来架设的网络服务有限，需要把网络中的一些交换机（包括网关交换机）升级为 交换机。由于改造的时间所限，只来得及把不超过 p台（含 p 台）交换机升级为 交换机，而所有剩下的交换机则需要通过改造网路的方法和这几台 交换机直接连接。但是无论是升级交换机还是改造网络都需要花费一定的。现在请你给出

2、一个改造网络的方案。使得按照该方案升级后每一个交换机要么是交换机，要么直接和交换机相连。并且要求提供的方案使改造所用的总费用最小。【任务描述】你的程序必须根据给定的输入，给出符合题意的输出：输入包括网络的拓扑结构，升级网络中每台交换机的费用，以及改造网络的费用，还有可以升级的交换机的最大数目p；你必须根据输入，找出一个升级的方案，满足升级后的交换机的数目不超过给定的可升级交换机最大值 p，且使得总费用最少；其中总费用的计算包括两个部分：一部分是升级交换机为交换机所需要的费用，该部分的费用按照所有的需要升级的交换机所需的费用之和来计算；另一部分是改造网络所需要的费用，该部分的费用按照所有未升级的

3、交换机到最近的交换机的网络路径距离之和来计算；注意：当网络中没有任何交换机升级到交换机的时候，由于也没有交换机可以连接到交换机，所以无穷大。定义此时的总费用为【输入格式】：(network.in)第一行为两个正整数 n（n 400）和 p，分别表示网络 换机的数目（交换机按照 1 到 n 标号）和可升级交换机的最大值。接下来的 n 行每行一个正整数ci，表示把标号为 i 的交换机升级为交换机所需要的费用。接下来的 n-1 行每行三个正整数 i、j、di,j（dij 20000），表示为 j 的交换机为为 i 的交换机的上层交换机，而di,j 表示两台交换机之间的网路距离。【输入样例】【输出格式

4、】：(network.out)你的输出第一行为一个整数 M，表示你的方案的最小总费用。接下来一行包括一个整数 p0，表示你的方案所需要升级为交换机的交换机数目。【输出样例】【运行限制】【评分方法】本题目一共有十个测试点，每个测试点的分数为总分数的 10%。对于每个测试点来说，如果你的分。正确，那么你将得到该测试点全部的分数，否则得 0注意，本题目的测试数据中有 8 个数据的 n 不超过。每点运行时间1 秒内存使用128M30222 1 23 2 46 5 27 5 9542 月亮森林【问题描述】一天早晨，一个小在森林里玩耍时看到一颗神奇的，光芒四射，还散发着一股淡淡的清香。很喜欢这颗，便把它捧

5、在手里带回了家。那天晚上，她说，她手里的做了一个梦，梦到一个面目慈祥的老。老对来自一棵月亮之树，原本只有在月亮上才能见到它，但是机缘巧合，喜欢这颗悄悄的落在了地球上，无法再回到月亮上了。老发现儿很种出，就问她是否愿意借助自己的勤劳和智慧，用这颗小小的一片茂密的月亮森林，让月亮树在地球上有一个温暖的新家兴奋地点点头，忙问老具体应该怎么做。老人解释说，这颗非同寻常，种下去的第二天上午就会长成一棵高度为1(一个)的小树苗。月亮树的生命力极强，以后还会每天上午长高一个。由于月亮树不同于地球上的生物，必须使用一种特殊的肥料才能对它施肥，而这种肥料老每天会送给儿一个。每天晚上，她必须给一棵树或者下午刚种下

6、去的施肥，但不能多施肥，也不能不施肥。被施肥的树或者在第二天上午将比一般情况下多长高一个，即两个。月亮树在成长的过有两个称为“收获点”的特殊高度，分别为 HP1 和 HP2。当月亮之树的高度第一次达到或者超过 HP1 的那天中午，树上就会结出一个果实。同样，当高度第一次达到或者超过 HP2 的那天中午，树上也会结出一个果实。果实里面有一颗种子, 和当初捡到的一模一样。每天下午，都可以选择一些种下去，种了恰好 M 棵树，且它们的高度都相同时，这些树才当然也可以不种。当能真正的适应地球的环境，的活下去。醒来后的那天下午，儿就按照老的吩咐把种下去了。她把完成老交付给任务作为一生中最大的心愿，日复一日

7、，年复一年辛勤的劳动着。她每天傍晚一坐在门槛上望着远方，眼前就会浮现出一片美丽而宽广的月亮森林。她坚信自己一定能成功，需要再长的时间也不怕。但是这一天何时才会来到呢？【输入文件】输入文件forest.in 仅包含三个整数 HP1,HP2,M（2=HP1HP2=20, 2=M=100）,代表两个收获点的高度和所需月亮树的棵数。【输出文件】输出文件forest.out 仅包含一个整数T，即最少需要的天数。【输入输出样例 1】【输入输出样例 2】forest.out84forest.in10156forest.out12forest.in4933 家园(HOMELAND.EXE)由于人类对自然的疯狂

8、破们在大约 2300 年之后，地球不能再居住了，于是在月球上建立了新的绿地，以便在需要时。令人意想不到的是，2177 年冬由于未知的原因，地球环境发生了连锁内迁往月球。，人类必须在最短的时间现有n 个太空站处于地球与月球之间（1.n），m 艘公共交通太空船在其中来回穿梭，每个太空站 Si 可容纳无限的人，每艘太空船 pi 只可容纳 Hpi 人。对于每一艘太空船pi，将周期性地停靠一系列的太空站（Si1,Si2Sir），如：（1， 3，4）表示停靠太空站 1 3 4 1 3 4 1 3 4 。 任一艘太空船从任一个太空站驶往另一个任意的太空站耗时为 1。人只能在太空船停靠太空站（或地球、月球）时上船或下船。初始时的人全在地球上，太空船全在初始站（太空船 pi 处于Si1），目标是让所有的人尽快地全部转移到月球上。输入：文件第一行为三个正整数 n（太空站个数）、 m（太空船个数）、 k（需要运送的地球上的人的个数），其中 1=m=13, 1=n=20, 1=k=50。接下来的 n 行给出了太空船的信息，第 i+1 行说明太空船 pi，此行第一个数表示 pi 可容纳的人数 Hpi，第二个数表示 pi 停靠一个周期的太空站个数 r，1=r=n+2, 随后r 个数便是停靠的太空站的(Si1,Si2,Sir), 地球用 0 表示，月球用-