#P8957. 「CGOI-3」巫泡弹弹乐

    ID: 8039 远端评测题 1000ms 512MiB 尝试: 0 已通过: 0 难度: 4 上传者: 标签>洛谷原创Special JudgeO2优化Ad-hoc

「CGOI-3」巫泡弹弹乐

题目背景

mc 正在挑战弹弹乐。

题目描述

弹弹乐由 nn 个弹力菇组成,每个弹力菇有 a,ba,b 两个属性。

对于弹力菇 ii 会向弹力菇 jj 连一条边权为 max(ai,aj)+max(bi,bj)\max(a_i,a_j)+\max(b_i,b_j) 的双向弹力通道。现在 mc 想知道弹力菇组成的图的最小生成树,以便他打破记录。

输入格式

第一行一个整数 nn

第二行 nn 个整数,第 ii 个数表示 aia_i

第三行 nn 个整数,第 ii 个数表示 bib_i

输出格式

第一行输出这个最小生成树的边权和。

接下来 n1n-1 行,每行输出两个整数表示一条树边。你可以输出任意一种合法方案。

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}$$
  • 对于 100%100\% 的数据,满足:1n1061\le n\le 10^61ai,bi1091\le a_i,b_i\le 10^9