比赛 20110318 评测结果 C
题目名称 公路修建 最终得分 0
用户昵称 Citron酱 运行时间 0.000 s
代码语言 Pascal 内存使用 0.00 MiB
提交时间 2011-03-18 20:52:09
显示代码纯文本
#include <fstream>
#include <iomanip>
#include <cmath>

#define I_F "roadz.in"
#define O_F "roadz.out"
#define MAXn 5000
#define FLOAT_MAX 3000000

using namespace std;

struct Points
{
	long x,y;
};

Points p[MAXn];
float map[MAXn][MAXn];
int n;
float ans;

void Input();
float sqr(float);
void GetMap();
void Prim();
void Output();

int main()
{
	Input();
	GetMap();
	Prim();
	Output();
	return 0;
}

void Input()
{
	ifstream fin(I_F);
	fin>>n;
	for (int i=0; i<n; fin>>p[i].x>>p[i++].y);
	fin.close();
}

float sqr(float x)
{
	return x*x;
}

void GetMap()
{
	for (int j,i=0; i<n; i++)
		for (j=0; j<n; map[i][j]=sqrt(sqr(p[i].x-p[j].x)+sqr(p[i].y-p[j++].y)));
}

void Prim()
{
	bool f[MAXn]={true};
	float t;
	int tn;
	for (int j,k,i=0; i<n-1; i++)
	{
		t=FLOAT_MAX;
		for (j=0; j<n; j++)
			if (f[j])
				for (k=0; k<n; k++)
					if ((!f[k])&&(map[j][k]<t))
					{
						t=map[j][k];
						tn=k;
					}
		f[tn]=true;
		ans+=t;
	}
}

void Output()
{
	ofstream fout(O_F);
	fout<<setprecision(2)<<setiosflags(ios::fixed)<<ans<<'\n';
	fout.close();
}