P1265 公路修建 (prim)
2024-08-31 07:50:55
题目描述
某国有n个城市,它们互相之间没有公路相通,因此交通十分不便。为解决这一“行路难”的问题,政府决定修建公路。修建公路的任务由各城市共同完成。
修建工程分若干轮完成。在每一轮中,每个城市选择一个与它最近的城市,申请修建通往该城市的公路。政府负责审批这些申请以决定是否同意修建。
政府审批的规则如下:
(1)如果两个或以上城市申请修建同一条公路,则让它们共同修建;
(2)如果三个或以上的城市申请修建的公路成环。如下图,A申请修建公路AB,B申请修建公路BC,C申请修建公路CA。则政府将否决其中最短的一条公路的修建申请;
(3)其他情况的申请一律同意。
一轮修建结束后,可能会有若干城市可以通过公路直接或间接相连。这些可以互相:连通的城市即组成“城市联盟”。在下一轮修建中,每个“城市联盟”将被看作一个城市,发挥一个城市的作用。
当所有城市被组合成一个“城市联盟”时,修建工程也就完成了。
你的任务是根据城市的分布和前面讲到的规则,计算出将要修建的公路总长度。
输入输出格式
输入格式:
第一行一个整数n,表示城市的数量。(n≤5000)
以下n行,每行两个整数x和y,表示一个城市的坐标。(-1000000≤x,y≤1000000)
输出格式:
一个实数,四舍五入保留两位小数,表示公路总长。(保证有惟一解)
输入输出样例
输入样例#1: 复制
4
0 0
1 2
-1 2
0 4
输出样例#1: 复制
6.47
code:
#include<cstdio>
#include<cmath>
using namespace std;
int n,cnt;
double sum;
int mst[5005];
double dis[5005][5005],mincost[5005];
struct point{
int x,y;
}city[5005];
double qdis(int a,int b){
// if(dis[a][b]) return dis[a][b];
// else
// return dis[a][b]=dis[b][a]=sqrt(abs(city[a].x-city[b].x)*abs(city[a].x-city[b].x)+abs(city[a].y-city[b].y)*abs(city[a].y-city[b].y));
return sqrt(abs(city[a].x-city[b].x)*abs(city[a].x-city[b].x)+abs(city[a].y-city[b].y)*abs(city[a].y-city[b].y));
}
void prim(int t){
if(cnt==n-1) return ;
cnt++;
int k; double minn=0x3f3f3f3f;
for(register int i=1;i<=n;i++) {
if(!mst[i]&&mincost[i]<minn){
minn=mincost[i];
k=i;
}
}
mst[k]=1;
for(register int i=1;i<=n;i++)
if(!mst[i]&&qdis(i,k)<mincost[i])
mincost[i]=qdis(i,k);
sum+=minn;
prim(k);
return ;
}
int main(){
scanf("%d",&n);
for(register int i=1;i<=n;i++)
scanf("%d %d",&city[i].x,&city[i].y);
for(register int i=2;i<=n;i++) mincost[i]=qdis(i,1);
mst[1]=1;
prim(1);
printf("%.2f",sum);
return 0;
}
最新文章
- 各类坐标系相互之间的转换(84互转GC02,GC02互转BD09)
- 初入网络系列笔记(6)TFTP协议
- golang开发缓存组件
- Python:如何显示进度条
- Java + eclipse + awt 编写锻炼打字小软件(未完成)
- oracle优化原则(二)
- RMQ问题ST算法 (还需要进一步完善)
- SynchronousQueue
- cocos2d-x之 CCSpriteBatchNode 用法总结
- Jmeter - foreach控制器之嵌套使用
- [置顶]
 xamarin android toolbar(踩坑完全入门详解)
- Mybatis使用MySQL进行模糊查询时输入中文检索不到结果
- 架构(一)JDK安装
- centos7进入单用户模式
- 设计模式のMediatorPattern(中介者模式)----行为模式
- Python字符串和列表的内置方法
- 给你的手机加上安全保障,请设置SIM卡PIN码
- TPS和QPS的区别和理解【转】
- Python基础+模块、异常
- PythonStudy——进制 System of numeration