比赛 |
HAOI2009 模拟试题3 |
评测结果 |
WEEEEEEEEE |
题目名称 |
公路修建 |
最终得分 |
0 |
用户昵称 |
苏轼 |
运行时间 |
0.000 s |
代码语言 |
Pascal |
内存使用 |
0.00 MiB |
提交时间 |
2009-04-23 11:16:01 |
显示代码纯文本
{
haoi2009 moni3 t2
time:2009.4.23
rp++
}
program cch(input,output);
const
maxf=10000000;
var
fa:array[1..5000] of longint;
n:longint;
map:array[1..5000,1..5000] of real;
v:array[1..5000] of boolean;
procedure init;
var
i,j:longint;
x,y:array[1..5000] of longint;
begin
assign(input,'roadz.in');
assign(output,'roadz.out');
reset(input);
rewrite(output);
readln(n);
for i:=1 to n do
readln(x[i],y[i]);
for i:=1 to n do
for j:=1 to n do
map[i,j]:=sqrt(sqr(x[i]-x[j])+sqr(y[i]-y[j]));
end;
function getfather(k:longint):longint;
begin
if k=fa[k] then exit(k);
fa[k]:=getfather(fa[k]);
exit(fa[k]);
end;
procedure main;
var
i,j,f,p,k,fi,fj,ch:longint;
a:array[1..5000] of longint;
dis,ans,min:real;
begin
for i:=1 to n do fa[i]:=i;
repeat
for i:=1 to n do a[i]:=0;
for f:=1 to n do
begin
dis:=maxf;
for i:=1 to n do
if getfather(i)=f then
for j:=1 to n do
if i<>j then
begin
fi:=getfather(i);
fj:=getfather(j);
if (fi<>fj)and(a[j]<>i) then
begin
if dis>map[i,j] then
begin
dis:=map[i,j];
k:=j; p:=i;
end
end;
end;
if dis<maxf then
begin ans:=ans+dis;
a[p]:=k;
end;
end;
for i:=1 to n do v[i]:=true;
for i:=1 to n do
if a[i]<>0 then
fa[getfather(i)]:=getfather(a[i]);
for i:=1 to n do
if v[i] and (a[i]<>0) then
begin
j:=i; min:=maxf;
repeat
if min>map[j,a[j]] then
min:=map[j,a[j]];
j:=a[j];
if v[j]=true then v[j]:=false
else break;
until (j=i)or(j=0);
if (min<maxf)and(j=i) then ans:=ans-min;
end;
ch:=0;
for i:=1 to n do
if getfather(i)=getfather(1) then inc(ch);
until ch=n;
writeln(ans:0:2);
close(input);
close(output);
end;
begin
init;
main;
end.