題意

Description

給出N個點的坐標，對它們建立一個最小生成樹，代價就是連接它們的路徑的長度，現要求總長度最小。N的值在100以內，坐標值在[-10000,10000].結果保留二位小數

Input

5 ---------------5個點
0 0 ---------------5個點點的坐標
0 1
1 1
1 0
0.5 0.5

Output

2.83

分析

先算出點與點之間的距離

距離=sqrt(sqr(x[i]-x[j])+sqr(y[i]-y[j]))

var
n,i,j,k,t:longint;
tj,min:real;
a:array[0..200,0..200]of real;
x,y:array[0..200]of real;
f:array[0..200]of longint;
begin
? ? readln(n);
? ? fillchar(a,sizeof(a),0);
? ? fillchar(f,sizeof(f),0);
? ? for i:=1 to n do
? ? readln(x[i],y[i]);
? ? for i:=1 to n do
? ? for j:=1 to n do
? ? a[i,j]:=sqrt(sqr(x[i]-x[j])+sqr(y[i]-y[j]));
? ? f[1]:=1;
? ? tj:=0;
? ? for i:=1 to n-1 do
? ? begin
? ? ? ? min:=maxlongint;
? ? ? ? for j:=1 to n do
? ? ? ? if f[j]=1 then
? ? ? ? ? for k:=1 to n do
? ? ? ? ? if f[k]=0 then
? ? ? ? ? if (a[j,k]<min)and(a[j,k]<>0) then
? ? ? ? ? begin
? ? ? ? ? ? ? min:=a[j,k];
? ? ? ? ? ? ? t:=k;
? ? ? ? ? end;
? ? ? ? if min<>maxint then
? ? ? ? begin
? ? ? ? ? ? tj:=tj+min;
? ? ? ? ? ? f[t]:=1;
? ? ? ? end;
? ? end;
? ? write(tj:0:2);
end.

轉載于:https://www.cnblogs.com/YYC-0304/p/9500147.html

總結

以上是生活随笔為你收集整理的剑鱼行动(普里姆算法)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。