等级：管理员
威望：50
文章：291
积分：669
注册：2003-05-18 |
 [更正]最小生成树
{最小生成树}
var f:text;
n:integer;
cost:array [1..100,1..100] of integer;
visited:array [1..100] of boolean;
procedure init;
var i,j:integer;
begin
assign(f,'graphjz.txt');
reset(f);
read(f,n);
for i:=1 to n do
for j:=1 to n do
read(f,cost[i,j]);
close(f);
end;
procedure prim;
var closest,lowcost:array [1..100] of integer;
i,j:integer;
min,minj:integer;
begin
for i:=2 to n do
begin
lowcost:=cost[1,i];
closest:=1;
end;
lowcost[1]:=1000;
for i:=2 to n do
begin
min:=1000;
for j:=1 to n do
if (lowcost[j]<min) and (lowcost[j]<>0) then
begin
min:=lowcost[j];
minj:=j;
end;
writeln(minj,' ',closest[minj],' ',min);
lowcost[minj]:=1000;
for j:=2 to n do
if ((lowcost[j]>cost[minj,j]) or (lowcost[j]=0)) and (lowcost[j]<>1000) and (cost[minj,j]<>0) then
begin
lowcost[j]:=cost[minj,j];
closest[j]:=minj;
end;
end;
end;
begin
init;
prim;
readln;
end. |
|
|
|
注册
趣题之家 → 信息学竞赛 → 算法艺术 → [更正]最小生成树
2003-10-02 16:58
