公路修建

题目链接

分析题意,可以发现,在(1)的条件下,(2)的情况是不会发生的,

于是直接求MST(Min Set Tree)

然而稠密图克鲁斯卡尔会TLE,建图还会爆空间,

所以用prime,用到时再计算距离即可

#include<bits/stdc++.h>
#define rep(i,r) for(int i=1;i<=r;i++)
#define Dis(a,b) (sqrt((x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b])))
#define N 5010
int n,fa[N];
double x[N],y[N],dis[N],ans;
bool vis[N];
double min(double a,double b) { return a<b?a:b; }
int main(){
scanf("%d",&n);
rep(i,n) scanf("%lf%lf",&x[i],&y[i]);
std::fill(dis,dis+n+,); dis[]=;
for(int i=;i<=n;i++){
int k=; rep(j,n)
if(!vis[j]&&dis[j]<dis[k]) k=j;
vis[k]=; ans+=dis[k];
rep(j,n) dis[j]=min(dis[j],Dis(k,j));
}
printf("%.2lf\n",ans); return ;
}

最新文章

  1. &gt;hibernate.cfg.xml的一些常用配置
  2. MVC 中301永久重定向
  3. appcache checking update
  4. 第17章课后题(高级Perl技巧)
  5. div盒布局
  6. Lucky7(容斥原理)
  7. Triangle(动态规划)
  8. Openresty的同步输出与流式响应
  9. P1462 通往奥格瑞玛的道路 (二分+最短路)
  10. Linux内存管理 (9)mmap(补充)
  11. SHA256withRSA证书签名,私钥签名/公钥验签
  12. Saiku相关异常处理(十五)
  13. iOS UI基础-19.0 UICollectionView
  14. 10. js时间格式转换
  15. 【基础练习】【区间DP】codevs1090 加分二叉树题解
  16. handler与anr机制
  17. along.js
  18. 【洛谷】P4585 [FJOI2015]火星商店问题
  19. kernel 4.4.12 移植 HUAWEI MU609 Mini PCIe Module
  20. POJ3281:Dining——题解

热门文章

  1. js判断触摸方向
  2. python移动多个子文件中的文件到一个文件夹
  3. pat00-自测5. Shuffling Machine (20)
  4. http状态代码含义收藏
  5. springboot整合rabbitmq,支持消息确认机制
  6. Java基础入门 - 简介
  7. 冒泡排序——Java实现
  8. hdu 2196 叶子节点最长距离(树DP)
  9. Python pip windows安装
  10. Android Activity中状态保存机制