洛谷 [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。。。。

巴特西

洛谷 [P1265] 公路修建

最新文章

热门文章