写在前面
本人CSDN博客主页:这里
一、题目
1、原题链接
3728. 城市通电
2、题目描述
平面上遍布着 n 座城市,编号 1∼n。
第 i 座城市的位置坐标为 (xi,yi)。
不同城市的位置有可能重合。
现在要通过建立发电站和搭建电线的方式给每座城市都通电。
一个城市如果建有发电站,或者通过电线直接或间接的与建有发电站的城市保持连通,则该城市通电。
在城市 i 建立发电站的花费为 ci 元。
在城市 i 与城市 j 之间搭建电线所需的花费为每单位长度 ki+kj 元。
电线只能沿上下左右四个方向延伸,电线之间可以相互交叉,电线都是双向的。
每根电线都是由某个城市沿最短路线搭建到另一个城市。
也就是说,如果在城市 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≤2000,1≤xi,yi≤106,1≤ci,ki≤109。输入样例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
二、解题报告
1、思路分析
思路来源:y总讲解视频
y总yyds
(1)建立一个虚拟源点,由虚拟源点向每个建有发电站的城市连一条边,边权为建立该发电站的花费。
(2)这样就转化为了一个最小生成树问题,求包括虚拟源点在内的图的最小生成树。
(3)利用prim算法进行求解即可。
2、时间复杂度
时间复杂度为O(n2+m)
3、代码详解
#include
#include
#include
#include
#include
using namespace std;
typedef long long LL;
typedef pair PII;
const int N=2010;
int n;
int c[N],k[N],fa[N]; //fa[]存储每个点的父结点,即建有发电站的城市
PII p[N]; //存储每个点的坐标,first为横坐标,second为纵坐标
LL dist[N]; //存储每个点到当前连通块的距离
bool st[N]; //存储每个点是否已经在连通块中
vector ans1; //存储所有需要建发电站的城市
vector ans2; //存储城市之间需要搭建电线的两个城市
//两点之间建设电线的花费
LL distance(int a,int b){ //注意类型,可能超过int范围
int x=abs(p[a].first-p[b].first);
int y=abs(p[a].second-p[b].second);
return (LL)(x+y)*(k[a]+k[b]);
}
//prim算法求最小生成树
LL prim(){ //注意返回类型,可能超过int范围
memset(dist,0x3f,sizeof dist);
dist[0]=0;
st[0]=true;
LL res=0;
//初始将0号点,虚拟源点已经加入连通块中,所以每个点到虚拟源点的距离(花费)为在该点建设发电站的花费
for(int i=1;idistance(j,t)){
dist[j]=distance(j,t);
fa[j]=t;
}
}
}
return res;
}
int main(){
cin>>n;
for(int i=1;i>p[i].first>>p[i].second;
for(int i=1;i>c[i];
for(int i=1;i>k[i];
cout
三、知识风暴
Prim算法
- 基本思想:先将起始点加入连通块中,然后寻找距离连通块最近的顶点然后再加入,同时利用该点更新其他点距离连通块的距离,然后再将距离连通块最近的点加入,循环往复,直到将所有点加入,得出最小生成树,如果没有将所有点都加入说明不存在最小生成树。
服务器托管,北京服务器托管,服务器租用 http://www.fwqtg.net
机房租用,北京机房租用,IDC机房托管, http://www.fwqtg.net