loj#P2835. 「JOISC 2018 Day 2」路网服务
「JOISC 2018 Day 2」路网服务
Cannot parse: undefinedms error parsing time
题目描述
译自 JOISC 2018 Day2 T2「道路網の整備 / Road Service」
IOI 王国有 个城市,编号为 到 。同时又有 条双向道路,编号为 到 。第 条道路连接城市 和城市 。在任意两个城市之间存在一条路径。
两个城市之间的距离定义为连接两个城市所经过的最少路径条数。IOI 王国的总距离定义为所有不同的城市对之间的距离。
IOI 王国的国王计划再建 条道路,以减少总距离,提高交通的便利性。
你作为国王的助理,请帮助国王找到一个好的方案。
任务
给定 IOI 王国现已存在的道路的信息和要建设的道路的条数,输出一个建设 条道路的方案。总距离最短分值越高。
输入格式
本题有 组输入。从每组数据中读取以下内容:
第一行包含三个被一个空格隔开的正整数 和 ,表示 IOI 王国有 座城市,国王计划建 条道路。 是评分用的参数;
接下来的 行,第 行包含两个正整数 ,表示第 条道路连接的两个城市。
输出格式
输出中输出 行。第 行包含两个整数 ,代表要建的道路连接的两个城市。
只需要提交输出即可。只有当输出格式符合上述描述时输出合法。
4 1 8
1 2
2 3
3 4
1 4
4 1 8
1 2
2 3
3 4
1 2
数据范围与提示
对于每组输出,你的得分按如下方式计算:
如果你的输出不符合输出格式要求,得 分。否则,设按你的计划建设道路后 IOI 王国的总距离为 ,并且设此数据点的分值为 。定义
这里,对于一个测试点,你得到的分数是
本题的分值是每组输出能获得的分值之和,分数取与这个分数之差的绝对值最小的整数。
对于每组数据, 的值如下:
输入编号 | ||||
---|---|---|---|---|