#P8483. 「HGOI-1」Build
「HGOI-1」Build
题目背景
一次旅行, 到了一个奇怪的小镇。
题目描述
这个小镇将要和周围的其他小镇一共 个小镇,一起修建一个能连通这 个小镇,有 条高速公路的交通网。其中每条高速公路都将会连接不同的两个小镇,即不存在一条高速公路的起点和终点相同。
但高速公路的修建费用是很高的,所以镇长们一致决定将共同承担高速公路的费用,所以他们希望修建的总费用最小。
而且由于不同小镇的基础设施建设情况不同,所以每个小镇在修建的费用也不同。经过协商,每条高速公路将由其所连接的两个小镇共同施工。每个小镇负责一半路程。为了同时结束整个施工过程,显然将会有小镇同时进行多条道路的施工,而施工的道路数量越多,所需要花费的价钱就越多。
经过计算,每个小镇施工的花费可以用函数表示,及对于小镇 ,有三个参数 ,,。对于 小镇来说在修建其第 条高速时,这条高速所需要的花费为 。
现在,这些镇长想要 给他们提供一个满足要求的建造方案,使总价格最小。
当然, 将这个问题交给了你。
输入格式
第一行两个整数 ,。
接下来 行,每行三个整数 ,,。
输出格式
共 行
第一行一个整数表示最小价格。
接下来 行,每行两个整数 ,,表示你提供的方案中的一条边。
4 4
1 2 3
2 3 4
3 4 5
4 5 6
114
1 2
1 2
1 3
3 4
提示
数据范围
本题采用捆绑测试,共有 个 ,最终分数为所有 分数之和。
$$\def\arraystretch{1.5} \begin{array}{|c|c|c|}\hline \textbf{Task} & \textbf{Score} & \textbf{特殊限制} \cr\hline 1 & 10 & n,m\le 500 \cr\hline 2 & 20 & n,m\le 5\times 10^3 \cr\hline 3 & 10 & \text{每个小镇的函数相同}\cr\hline 4 & 20 & a_i=0 \cr\hline 5 & 20 & m=n-1 \cr\hline 6 & 20 & \cr\hline \end{array} $$对于 的数据,, ,,,。
数据保证最小价格在 范围内。
说明
本题有 ,价格正确可以获得 的分数。每个 取其中所有数据点得分的最小值。
如果你不会构造方案,也请你再输出最小价格后输出 行,每行两个 范围内的整数,防止 出现错误。