比赛 |
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);
}