#P8957. 「CGOI-3」巫泡弹弹乐
「CGOI-3」巫泡弹弹乐
题目背景
mc 正在挑战弹弹乐。
题目描述
弹弹乐由 个弹力菇组成,每个弹力菇有 两个属性。
对于弹力菇 会向弹力菇 连一条边权为 的双向弹力通道。现在 mc 想知道弹力菇组成的图的最小生成树,以便他打破记录。
输入格式
第一行一个整数 。
第二行 个整数,第 个数表示 。
第三行 个整数,第 个数表示 。
输出格式
第一行输出这个最小生成树的边权和。
接下来 行,每行输出两个整数表示一条树边。你可以输出任意一种合法方案。
3
1 2 1
3 2 3
9
1 2
1 3
提示
数据范围
「本题采用捆绑测试」
$$\def{\arraystretch}{1.5}\begin{array}{|c|c|c|c|}\hline \textbf{Subtask} & \bm{n} & \textbf{特殊性质} & \textbf{分值}\cr\hline 1 & n\le 500 & \text{无} & 20 \cr\hline 2 & n\le 5\times 10^4 & \text{无} & 20\cr\hline 3 & \text{无特殊限制} & \text{数据随机} & 20\cr\hline 4 & \text{无特殊限制} & \text{无} & 40 \cr\hline \end{array}$$- 对于 的数据,满足:,。