#2835. 「JOISC 2018 Day 2」路网服务

题目类型:答案提交 评测方式:Special Judge
上传者: HeRaNO

题目描述

译自 JOISC 2018 Day2 T2「道路網の整備 / Road Service

IOI 王国有 N 个城市,编号为 1 N 。同时又有 N-1 条双向道路,编号为 1 N-1 。第 i 条道路连接城市 A_i 和城市 B_i 。在任意两个城市之间存在一条路径。

两个城市之间的距离定义为连接两个城市所经过的最少路径条数。IOI 王国的总距离定义为所有不同的城市对之间的距离。

IOI 王国的国王计划再建 K 条道路,以减少总距离,提高交通的便利性。

你作为国王的助理,请帮助国王找到一个好的方案。

任务

给定 IOI 王国现已存在的道路的信息和要建设的道路的条数,输出一个建设 K 条道路的方案。总距离最短分值越高。

输入格式

本题有 6 组输入。从每组数据中读取以下内容:

第一行包含三个被一个空格隔开的正整数 N,K W_0 ,表示 IOI 王国有 N 座城市,国王计划建 K 条道路。 W_0 是评分用的参数;

接下来的 N-1 行,第 i 行包含两个正整数 A_i,B_i ,表示第 i 条道路连接的两个城市。

输出格式

输出中输出 K 行。第 j 行包含两个整数 X_j,Y_j ,代表要建的道路连接的两个城市。

只需要提交输出即可。只有当输出格式符合上述描述时输出合法。

样例

样例输入 1
4 1 8
1 2
2 3
3 4

样例输出 1

1 4

样例说明 1

在原有道路的基础上再建一条 1 号城市到 4 号城市的道路,总距离就变成了 8

设这组数据 P=10 。这里 S=0 S 的定义参见「数据范围与提示」),因此这组输出的得分为 10 分。

样例输入 2

4 1 8
1 2
2 3
3 4

样例输出 2

1 2

样例说明 2

在建设这条道路之后,总距离变成了 10

设这组数据 P=10 ,此处 S=-0.25 ,因此得分为 4.728\cdots 分。

数据范围与提示

对于每组输出,你的得分按如下方式计算:

如果你的输出不符合输出格式要求,得 0 分。否则,设按你的计划建设道路后 IOI 王国的总距离为 W ,并且设此数据点的分值为 P 。定义

S=1.0-\frac{W}{W_0}

这里,对于一个测试点,你得到的分数是

\min(P,P\times 20^{S})

本题的分值是每组输出能获得的分值之和,分数取与这个分数之差的绝对值最小的整数。

对于每组数据, N,K,W_0,P 的值如下:

输入编号 N K W_0 P
1 20 4 512 10
2 1000 100 2650000 18
3 300 1755000
4 100 2900000
5 2690000
6 300 1745000
编辑器加载中 …