J12 习题-3 城市通电

题目描述

平面上遍布着 $n$ 座城市，编号 $1 \sim n$。 第 $i$ 座城市的位置坐标为 $(x_i,y_i)$。 不同城市的位置有可能重合。 现在要通过建立发电站和搭建电线的方式给每座城市都通电。 一个城市如果建有发电站，或者通过电线直接或间接的与建有发电站的城市保持连通，则该城市通电。 在城市 $i$ 建立发电站的花费为 $c_i$ 元。 在城市 $i$ 与城市 $j$ 之间搭建电线所需的花费为每单位长度 $k_i+k_j$ 元。 电线只能沿上下左右四个方向延伸，电线之间可以相互交叉，电线都是双向的。 每根电线都是由某个城市沿最短路线搭建到另一个城市。 也就是说，如果在城市 $i$ 与城市 $j$ 之间搭建电线，则电线的长度为 $|x_i-x_j|+|y_i-y_j|$。 请问，如何合理设计通电方案，可以使得所有城市都成功通电，且花费最少？ 输出最少花费和具体方案。

输入格式

第一行包含整数 $n$。 接下来 $n$ 行，其中第 $i$ 行包含两个整数 $x_i,y_i$，用来描述城市 $i$ 的横纵坐标。 再一行包含 $n$ 个整数 $c_1,c_2,…,c_n$，用来描述每个城市建立发电站的花费。 最后一行包含 $n$ 个整数 $k_1,k_2,…,k_n$。

输出格式

第一行输出所需要的最少花费。 第二行输出一个整数 $v$，表示需要建立发电站的数量。 第三行输出 $v$ 个整数，表示建立发电站的城市编号，注意输出编号要在范围 $[1,n]$ 内。且输出编号不应重复。 第四行输出一个整数 $e$，表示需要搭建的电线数量。 接下来 $e$ 行，每行输出两个整数 $a,b$，表示要在城市 $a$ 和 $b$ 之间搭建电线。注意，任意两个城市之间最多只需要搭建一根电线，也就是说，对于每个 $(a,b)$，不要有多余的 $(a,b)$ 或 $(b,a)$ 输出。$a$ 和 $b$ 不能相同，且要在范围 [1,n] 内。 如果答案唯一，输出编号顺序从小到大，输出电线顺序起点编号从小到大。

输入样例1

3
2 3
1 1
3 2
3 2 3
3 2 3

输出样例1

8
3
1 2 3 
0

输入样例2

3
2 1
1 2
3 3
23 2 23
3 2 3

输出样例2

27
1
2 
2
1 2
2 3

样例分析

如上所示。

数据范围

对于 $100\%$ 的数据： 对于前三个测试点，$1 \le n \le 3$。 对于全部测试点，$1 \le n \le 2000$，$1 \le x_i,y_i \le 10^6$，$1 \le c_i,k_i \le 10^9$。