題意

學校有n臺計算機，為了方便數據傳輸，現要將它們用數據線連接起來。兩臺計算機被連接是指它們之間有數據線連接。由于計算機所處的位置不同，因此不同的兩臺計算機的連接費用往往是不同的。
當然，如果將任意兩臺計算機都用數據線連接，費用將是相當龐大的。為了節省費用，我們采用數據的間接傳輸手段，即一臺計算機可以間接的通過若干臺計算機（作為中轉）來實現與另一臺計算機的連接。
現在由你負責連接這些計算機，你的任務是使任意兩臺計算機都連通（不管是直接的或間接的）。?

分析

這題其實就是最短網絡

一個一個點枚舉，如果它小于min，并且它不等于0，那么min=這個點，記錄下這個點

var
n,tj,i,j,k,x,y,t,min:longint;
a:array[0..200,0..200]of longint;
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
? ? for j:=1 to n do
? ? read(a[i,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);
end.

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

總結

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

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