【洛谷P1265】公路修建
2024-10-21 14:36:52
公路修建
分析题意,可以发现,在(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 ;
}
最新文章
- >;hibernate.cfg.xml的一些常用配置
- MVC 中301永久重定向
- appcache checking update
- 第17章课后题(高级Perl技巧)
- div盒布局
- Lucky7(容斥原理)
- Triangle(动态规划)
- Openresty的同步输出与流式响应
- P1462 通往奥格瑞玛的道路 (二分+最短路)
- Linux内存管理 (9)mmap(补充)
- SHA256withRSA证书签名,私钥签名/公钥验签
- Saiku相关异常处理(十五)
- iOS UI基础-19.0 UICollectionView
- 10. js时间格式转换
- 【基础练习】【区间DP】codevs1090 加分二叉树题解
- handler与anr机制
- along.js
- 【洛谷】P4585 [FJOI2015]火星商店问题
- kernel 4.4.12 移植 HUAWEI MU609 Mini PCIe Module
- POJ3281:Dining——题解