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

「JOISC 2018 Day 2」路网服务

Cannot parse: undefinedms error parsing time

题目描述

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

IOI 王国有 NN 个城市,编号为 11NN。同时又有 N1N-1 条双向道路,编号为 11N1N-1。第 ii 条道路连接城市 AiA_i 和城市 BiB_i。在任意两个城市之间存在一条路径。

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

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

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

任务

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

输入格式

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

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

接下来的 N1N-1 行,第 ii 行包含两个正整数 Ai,BiA_i, B_i,表示第 ii 条道路连接的两个城市。

输出格式

输出中输出 KK 行。第 jj 行包含两个整数 Xj,YjX_j, Y_j,代表要建的道路连接的两个城市。

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

4 1 8
1 2
2 3
3 4
1 4
4 1 8
1 2
2 3
3 4
1 2

数据范围与提示

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

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

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

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

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

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

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

输入编号 NN KK W0W_0 PP
11 2020 44 512512 1010
22 10001000 100100 26500002650000 1818
33 300300 17550001755000
44 100100 29000002900000
55 26900002690000
66 300300 17450001745000