題意

農民約翰被選為他們鎮的鎮長！他其中一個競選承諾就是在鎮上建立起互聯網，并連接到所有的農場。當然，他需要你的幫助。約翰已經給他的農場安排了一條高速的網絡線路，他想把這條線路共享給其他農場。為了用最小的消費，他想鋪設最短的光纖去連接所有的農場。你將得到一份各農場之間連接費用的列表，你必須找出能連接所有農場并所用光纖最短的方案。每兩個農場間的距離不會超過100000 ?

分析

這題我是用普里姆算法

一個一個點枚舉，如果它小于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/9500152.html

總結

以上是生活随笔為你收集整理的USACO 3.1 Agri-Net 最短网络 (最小生成树)(普里姆算法)的全部內容，希望文章能夠幫你解決所遇到的問題。

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