记录编号	9974	评测结果	AWWWWTTTTT
题目名称	公路修建	最终得分	10
用户昵称	苏轼	是否通过	未通过
代码语言	Pascal	运行时间	5.228 s
提交时间	2009-04-23 12:51:12	内存使用	171.78 MiB

{
 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 real;
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:=0;
     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<>0)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.