woshiniba 2008-09-23 04:16:00
点我顶贴
收藏
删除
源代码：program newzxscs；
var
cost:array [0..1010,0..1010] of longint；
lowcost,closest:array [0..1010] of longint；
i,j,n,m,qd,zd,all,jz:longint；
procedure prim(v0:integer)；
var
i,j,k,min:integer；
begin
for i:=1 to n do begin
lowcost[i]:=cost[v0,i]；
closest[i]:=v0；
end；
for i:=2 to n do
begin
min:=maxint；
for j:=1 to n do
if (min>lowcost[j]) and (lowcost[j]<>0) then begin
min:=lowcost[j]；
k:=j；
end；
lowcost[k]:=0；
for j:=1 to n do
if (cost[k,j]<lowcost[j])and(lowcost[j]<>0) then begin
lowcost[j]:=cost[k,j]；
closest[j]:=k；
end；
end；
end；
begin
read(n)；
for i:=1 to n do
for j:=1 to n do
begin
read(cost[i,j])；
if i=j then cost[i,j]:=maxlongint；
end；
prim(1)；
for i:=2 to n do
all:=all+cost[i,closest[i]]；
writeln(all)；
readln；readln；
end.