某大学准备在校园网中构建校园网络，已知在校园网中选好了N（N<1000）个点，并准备在这些点安装网络设备和电脑。若要将N个点互相连接起来，问怎样布线才能使得总距离最短，两点间的布线长度等于这两个点的几何距离。【输入】network.in输入文件的第一行为一个正整数N(1≤N≤100)。接下来N行，每行2个数U,V ，表示坐标。【输出】network.out输出最短路径距离（保留两位小数）【样例数据】 【输入】50 00 10 -11 0-1 0【输出】4.00
{思路分析：此题可以应用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.
开心洋葱 , 版权所有丨如未注明 , 均为原创丨未经授权请勿修改 , 转载请注明Pascal经典算法详解-网络设计问题！
