[Delphi (Object Pascal)] Pascal经典算法详解-网络设计问题 →→→→→进入此内容的聊天室

来自 , 2021-03-19, 写在 Delphi (Object Pascal), 查看 106 次.
URL http://www.code666.cn/view/614594c3
  1. {思路分析:此题可以应用PRIM算法解决,关键是根据输入文件算出图的邻接矩阵,然后可以直接应用PRIM算法。}
  2. program network;
  3. const
  4.   vmax=100;
  5. var
  6.     w:array[1..vmax,1..vmax]of real;
  7.     x,y:array[1..vmax] of real;
  8.     i,j,k,v,e:integer;
  9.     sum:real;
  10. procedure prim(v0:integer);
  11.   var
  12.     flag:array[1..vmax] of boolean;
  13.     min:real;
  14.     prevk,nextk:integer;
  15.   begin
  16.     fillchar(flag,sizeof(flag),false);
  17.     flag[v0]:=true;
  18.     for i:=1 to v-1 do
  19.       begin
  20.         min:=1e38;
  21.         for k:=1 to v do
  22.           if flag[k] then
  23.              for j:=1 to v do
  24.                 if (not flag[j]) and (w[k,j]<min) and (w[k,j]<>0)
  25.                  then begin
  26.                      min:=w[k,j];
  27.                      nextk:=j;
  28.                      prevk:=k;
  29.                    end;
  30.          if min<>1e10
  31.             then begin
  32.                    flag[nextk]:=true;
  33.                    {writeln(prevk,' ',nextk,' ',min:0:2);    此部分输出每个结点对的距离,因题目不要求所以不输出。}
  34.                    sum:=sum+min;
  35.                  end;
  36.       end;
  37.   end;{prim}
  38. begin
  39.   assign(input,'network.in');
  40.   reset(input);
  41.   assign(output,'network.out');
  42.   rewrite(output);
  43.   fillchar(w,sizeof(w),0);
  44.   readln(v);
  45.   for i:=1 to v do
  46.     readln(x[i],y[i]);
  47.   for i:=1 to v do                                           {计算图的邻接矩阵}
  48.     begin
  49.     for j:=i+1 to v do
  50.        begin
  51.          w[i,j]:=sqrt(sqr(x[i]-x[j])+sqr(y[i]-y[j]));
  52.          w[j,i]:=w[i,j];
  53.        end;
  54.     end;
  55.    sum:=0;
  56.     prim(1);
  57.     writeln(sum:0:2);
  58.   close(input);
  59.   close(output);
  60. end.
  61. //delphi/7191

回复 "Pascal经典算法详解-网络设计问题"

这儿你可以回复上面这条便签

captcha