光伏电站建设的国家网站,网校搭建平台,鹰潭城乡建设局的网站,360网页版登录入口acwing3728 蓝桥杯集训每日一题
平面上遍布着 n 座城市#xff0c;编号 1∼n。
第 i 座城市的位置坐标为 (xi,yi)
不同城市的位置有可能重合。
现在要通过建立发电站和搭建电线的方式给每座城市都通电。
一个城市如果建有发电站#xff0c;或者通过电线直接或间接的与建…acwing3728 蓝桥杯集训每日一题
平面上遍布着 n 座城市编号 1∼n。
第 i 座城市的位置坐标为 (xi,yi)
不同城市的位置有可能重合。
现在要通过建立发电站和搭建电线的方式给每座城市都通电。
一个城市如果建有发电站或者通过电线直接或间接的与建有发电站的城市保持连通则该城市通电。
在城市 i 建立发电站的花费为 ci 元。
在城市 i 与城市 j 之间搭建电线所需的花费为每单位长度 kikj 元。
电线只能沿上下左右四个方向延伸电线之间可以相互交叉电线都是双向的。
每根电线都是由某个城市沿最短路线搭建到另一个城市。
也就是说如果在城市 i 与城市 j 之间搭建电线则电线的长度为 |xi−xj||yi−yj|。
请问如何合理设计通电方案可以使得所有城市都成功通电且花费最少
输出最少花费和具体方案。
如果方案不唯一则输出任意一种合理方案均可。
输入格式
第一行包含整数 n。
接下来 n 行其中第 i 行包含两个整数 xi,yi用来描述城市 i 的横纵坐标。
再一行包含 n 个整数 c1,c2,…,cn用来描述每个城市建立发电站的花费。
最后一行包含 n 个整数 k1,k2,…,kn。
输出格式
第一行输出所需要的最少花费。
第二行输出一个整数 v表示需要建立发电站的数量。
第三行输出 v 个整数表示建立发电站的城市编号注意输出编号要在范围 [1,n]内。且输出编号不应重复。输出编号顺序随意。
第四行输出一个整数 e表示需要搭建的电线数量。
接下来 e 行每行输出两个整数 a,b表示要在城市 a 和 b 之间搭建电线。注意任意两个城市之间最多只需要搭建一根电线也就是说对于每个 (a,b)不要有多余的 (a,b) 或 (b,a) 输出。a 和 b 不能相同且要在范围 [1,n]内。输出电线顺序随意。
如果答案不唯一输出任意合理方案即可。
数据范围
对于前三个测试点1≤n≤3。 对于全部测试点1≤n≤20001≤xi,yi≤10^61≤ci,ki≤10^9。
输入样例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难度困难时/空限制2s / 256MB总通过数594总尝试数1351来源AcWing,第5场周赛算法标签 最小生成树Prim
考虑到最小生成树的prim算法
本题要将所有城市连接起来两种方式一是直接连接发电站花费为c[i]二是连接一个城市该城市已经直接连接或者间接连接发电站。
ans1数组存建立发电站的城市序号ans2存连接在两城市之间的电路
考虑用pair形式存储该点连接的城市还是发电站 以及 花费
代码详解如下 prim算法 前面为初始化表示一个超级原点并初始化所有dist[i] 为直接在该城市建立发电站的花费c[i]。 接下来迭代n次找到距离最近并且不在集合内的点放入集合最后用该点更新其他所有的点
