【洛谷P1265】公路修建

公路修建

题目链接

分析题意,可以发现,在(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 ;
}
上一篇:sobel算法的Soc FPGA实现之框架分析(二)


下一篇:【原创】Linux PCI驱动框架分析(二)