#CW52. 湖上的前线基地(network)
湖上的前线基地(network)
题目描述
有 台机器,编号为 。把编号看作 位二进制数。给定长度为 的非负整数序列 。编号为 的不同机器之间可以铺设管道,费用为 ,要求铺设管道后任意两台机器连通,求最小总费用,并输出任意一种达到最小费用的方案。
输入格式
从 network.in 文件读入数据。
第一行一个整数 。第二行给出 个非负整数 。
输出格式
将结果输出到 network.out 文件。
第一行输出管道数量 。接下来 行输出两个不同的机器编号 ,表示铺设一条管道。最后一行输出最小总费用。输出任意一棵达到最小费用的生成树即可。
样例 1 输入
2
4 3 2 1
样例 1 输出
3
2 3
1 3
0 1
9
数据范围
保证 ,。
本题采用子任务捆绑计分:一个子任务中的全部测试点均通过后,才能获得该子任务的分数。各子任务分数可以累加。
本题采用特殊判定(SPJ):输出任意一棵达到最小费用的生成树均可。
| 子任务 | 分值 | 测试点 | 附加条件 |
|---|---|---|---|
| 1 | 10 | ||
| 2 | 15 | ||
| 3 | 20 | ||
| 4 | 25 | ,序列 随机生成 | |
| 5 | 30 |