{思路分析:此题可以应用PRIM算法解决,关键是根据输入文件算出图的邻接矩阵,然后可以直接应用PRIM算法。}
program network;
const
vmax=100;
var
w:array[1..vmax,1..vmax]of real;
x,y:array[1..vmax] of real;
i,j,k,v,e:integer;
sum:real;
procedure prim(v0:integer);
var
flag:array[1..vmax] of boolean;
min:real;
prevk,nextk:integer;
begin
fillchar(flag,sizeof(flag),false);
flag[v0]:=true;
for i:=1 to v-1 do
begin
min:=1e38;
for k:=1 to v do
if flag[k] then
for j:=1 to v do
if (not flag[j]) and (w[k,j]<min) and (w[k,j]<>0)
then begin
min:=w[k,j];
nextk:=j;
prevk:=k;
end;
if min<>1e10
then begin
flag[nextk]:=true;
{writeln(prevk,' ',nextk,' ',min:0:2); 此部分输出每个结点对的距离,因题目不要求所以不输出。}
sum:=sum+min;
end;
end;
end;{prim}
begin
assign(input,'network.in');
reset(input);
assign(output,'network.out');
rewrite(output);
fillchar(w,sizeof(w),0);
readln(v);
for i:=1 to v do
readln(x[i],y[i]);
for i:=1 to v do {计算图的邻接矩阵}
begin
for j:=i+1 to v do
begin
w[i,j]:=sqrt(sqr(x[i]-x[j])+sqr(y[i]-y[j]));
w[j,i]:=w[i,j];
end;
end;
sum:=0;
prim(1);
writeln(sum:0:2);
close(input);
close(output);
end.
//delphi/7191