洛谷 [P1265] 公路修建
本题的描述：城市联盟，最短距离。。
使人想到了prim求MST，再一看数据范围：完全图！，那么一定得用prim，因为只有5000个点，所以不加优化的prim就能过。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <cmath>
using namespace std;
const int MAXN=5005;
int init(){
int rv=0,fh=1;
char c=getchar();
while(c<\'0\'||c>\'9\'){
if(c==\'-\') fh=-1;
c=getchar();
}
while(c>=\'0\'&&c<=\'9\'){
rv=(rv<<1)+(rv<<3)+c-\'0\';
c=getchar();
}
return rv*fh;
}
int n,x[MAXN],y[MAXN];
double dis[MAXN],tot;
bool f[MAXN];
double cal(int a,int b){
double r1=x[a]-x[b],r2=y[a]-y[b];
return sqrt(r1*r1+r2*r2);
}
int main(){
freopen("in.txt","r",stdin);
n=init();
for(int i=1;i<=n;i++){
x[i]=init();y[i]=init();
}
memset(dis,0x7f,sizeof(dis));
dis[1]=0.0;
f[1]=1;
for(int i=2;i<=n;i++){
dis[i]=cal(1,i);
}
for(int k=2;k<=n;k++){
double mi=1e20;
int t=0;
for(int i=1;i<=n;i++){
if(!f[i]){
if(dis[i]<mi) {mi=dis[i];t=i;}
}
}
if(t==0) break;
tot+=mi;
f[t]=1;
for(int i=1;i<=n;i++){
if(!f[i]){
dis[i]=min(dis[i],cal(t,i));
}//在这里写的时候有一种dijkstra的感觉，但要注意这里的dis[]表示的是到已生成的MST的距离，
不是到某一点的距离。
}
}
printf("%.2lf",tot);
fclose(stdin);
return 0;
}
noip完了之后要学堆优化prim。。。。
版权声明：本文为Mr-WolframsMgcBox原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。