比赛 HAOI2009 模拟试题3 评测结果 MMMMMMMMMM
题目名称 公路修建 最终得分 0
用户昵称 Citron酱 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2012-06-28 16:56:00
显示代码纯文本
#include <cstdio>
#include <cmath>

#define I_F "roadz.in"
#define O_F "roadz.out"

struct point
{
	long x,y;
};
struct edge
{
	double l;
	int x,y;
};

const int MAXn=5000;

point s[MAXn];
edge h[MAXn*(MAXn-1)/2+1];
long l;
double ans=0;
int n;

void Input();
inline double Sqr(const double&);
template<typename Any>
inline void Swap(Any&, Any&);
void Prework();
void Delete();
int Root(const int*, const int&); 
void Union(int*, const int&, const int&);
void Kaaala();
void Output();

int main()
{
	Input();
	Prework();
	Kaaala();
	Output();
	return 0;
}

void Input()
{
	freopen(I_F,"r",stdin);
	scanf("%d",&n);
	for (int i=0; i<n; ++i)
		scanf("%ld%ld",&s[i].x,&s[i].y);
}

inline double Sqr(const double &x)
{
	return x*x;
}

template<typename Any>
inline void Swap(Any &a, Any &b)
{
	Any t=a;
	a=b;
	b=t;
}

void Prework()
{
	l=0;
	for (int i=0; i<n-1; ++i)
		for (int j=i+1; j<n; ++j)
		{
			h[++l].l=sqrt(Sqr(s[i].x-s[j].x)+Sqr(s[i].y-s[j].y));
			h[l].x=i;
			h[l].y=j;
			
			for (int k=l; k>1 && h[k].l<h[k/2].l; k/=2)
				Swap(h[k],h[k/2]);
		}
}

void Delete()
{
	h[1]=h[l--];
	for (int x=1; ;)
		if (x*2>l)
			break;
		else
			if (x*2==l)
			{
				if (h[x].l>h[l].l)
					Swap(h[x],h[l]);
				break;
			}
			else
				if (h[x*2].l<h[x*2+1].l)
					if (h[x].l>h[x*2].l)
					{
						Swap(h[x],h[x*2]);
						x*=2;
					}
					else
						break;
				else
					if (h[x].l>h[x*2+1].l)
					{
						Swap(h[x],h[x*2+1]);
						x=x*2+1;
					}
					else
						break;
}

int Root(const int *s, const int &x)
{
	return (s[x]==x)?x:Root(s,s[x]);
}

void Union(int *s, const int &a, const int &b)
{
	if (s[b]==b)
		s[b]=a;
	if (s[a]!=s[b])
	{
		Union(s,s[a],s[b]);
		s[b]=s[a];
	}
}

void Kaaala()
{
	int s[MAXn];
	for (int i=0; i<n; ++i)
		s[i]=i;
	
	for (int i=1; i<n; ++i)
	{
		while (Root(s,h[1].x)==Root(s,h[1].y))
			Delete();
		ans+=h[1].l;
		Union(s,h[1].x,h[1].y);
		Delete();
	}
}

void Output()
{
	freopen(O_F,"w",stdout);
	printf("%.2lf\n",ans);
}