#CW52. 湖上的前线基地(network)

湖上的前线基地(network)

题目描述

有 2n2^n 台机器,编号为 0,1,…,2n−10, 1, \dots, 2^n - 1。把编号看作 nn 位二进制数。给定长度为 2n2^n 的非负整数序列 aa。编号为 i,ji, j 的不同机器之间可以铺设管道,费用为 a[i&j]a[i \& j],要求铺设管道后任意两台机器连通,求最小总费用,并输出任意一种达到最小费用的方案。

输入格式

从 network.in 文件读入数据。

第一行一个整数 nn。第二行给出 2n2^n 个非负整数 a0,a1,…,a2n−1a_0, a_1, \dots, a_{2^n-1}。

输出格式

将结果输出到 network.out 文件。

第一行输出管道数量 mm。接下来 mm 行输出两个不同的机器编号 u,vu, v,表示铺设一条管道。最后一行输出最小总费用。输出任意一棵达到最小费用的生成树即可。

样例 1 输入

2
4 3 2 1

样例 1 输出

3
2 3
1 3
0 1
9

数据范围

保证 1≤n≤201 \le n \le 20,0≤ai≤1090 \le a_i \le 10^9。

本题采用子任务捆绑计分:一个子任务中的全部测试点均通过后,才能获得该子任务的分数。各子任务分数可以累加。

本题采用特殊判定(SPJ):输出任意一棵达到最小费用的生成树均可。

子任务 分值 测试点 附加条件
1 10 1∼31\sim 3 n≤4n \le 4
2 15 4∼64\sim 6 n≤10n \le 10
3 20 7∼107\sim 10 n≤14n \le 14
4 25 11∼1511\sim 15 n≤20n \le 20,序列 aa 随机生成
5 30 16∼2016\sim 20 n≤20n \le 20