图论的实际应用之一 最小生成树 (300分)

有n个村庄，现在要给这些村庄安装有线电视。有个矩阵a[n, n]表示修建线路的费用，其中a[i, j]表示i村庄到j村庄铺设线路的费用，显然a[i, j]=a[j, i]。对于给定的费用矩阵a，编程求给n个村庄都通上有线电视的费用最小的方案。
下一题:
http://www.delphibbs.com/delphibbs/dispq.asp?lid=1949490

好像有个N算法，我先试着写个简单的

把教材上的两个都写出来就拿满分了。
不过，拿了之后还有等着你的东东。

……
我常用一个的

用TP7.0编的
const maxn=20;
type node=record
cost:real;
index:integer;
end;
var dist:array[1..maxn,1..maxn] of real;
s:array[1..maxn] of boolean;
cost:array[1..maxn] of node;
i,j,k,n,min:integer;
mindist,mincost:real;
begin
read;
for i:=1 to ndo
for j:=1 to ndo
begin
read(dist[i,j]);
if dist[i,j]=0 then
dist[i,j]:=maxint*maxint;
end;
fillchar(s,sizeof(s),0);
s[1]:=true;
mincost:=0;
for i:=1 to ndo
if s then
cost.cost:=maxint*maxint else
cost.cost:=dist[1,i];
for i:=1 to ndo
cost.index:=1;
for k:=2 to ndo
begin
mindist:=maxint*maxint;
for j:=1 to ndo
if not s[j] then
if cost[j].cost<mindist then
begin
mindist:=cost[j].cost;
min:=j;
end;
s[min]:=true;
mincost:=mincost+dist[min,cost[min].index];
writeln(min,'-->',cost[min].index);
cost[min].cost:=maxint*maxint;
for i:=1 to ndo
if not s then
if cost.cost>dist[min,i] then
begin
cost.cost:=dist[min,i];
cost.index:=min;
end;
end;
writeln(mincost);
end.

我的解法
代碼如下(修改了一下求中心點的)：
{$APPTYPE CONSOLE}
program mintree;
const max=100;
var v:array[1..max,1..max] of real;
s:array[1..max] of boolean;
alv:array[1..max] of integer;
i,j,k,n,vi,vj:integer;
min,mincost:real;
begin
vi:=0;
vj:=0;
read;
for i:=1 to ndo
for j:=1 to ndo
begin
read(v[i,j]);
if v[i,j]=0 then
v[i,j]:=maxint;
end;
fillchar(s,sizeof(s),0);
min:=maxint;
mincost:=0;
for i:=1 to ndo
for j:=1 to ndo

if v[i,j]<min then
begin
min:=v[j,j];
vi:=i;
vj:=j;
end;
alv[1]:=vi;
alv[2]:=vj;
s[vi]:=true;
s[vj]:=true;
writeln(vi,vj);
mincost:=mincost+v[vi,vj];
k:=3;
while(k<=n)do
begin
min:=maxint;
for i:=1 to ndo
begin
if s then
continue;
for j:=1 to k-1do

begin
if v[i,alv[j]]<min then
begin
min:=v[i,alv[j]];
vi:=i;
vj:=alv[j];
end;
end;
end;
alv[k]:=vi;
s[vi]:=true;
writeln(vi,vj);
mincost:=mincost+v[vi,vj];
k:=k+1;
end;

writeln(mincost);
end.

其他幾個問題一時搞不定

搞不定也没关系,我暂时就不再出新题了,等搞定了这几个再说.

可能明天开始，我们学校就要开课了，估计半个月之内不能上忘了[]

發現前面的有點錯誤
修改如下：
{$APPTYPE CONSOLE}
program mintree;
const max=100;
var v:array[1..max,1..max] of real;
s:array[1..max] of boolean;
alv:array[1..max] of integer;
i,j,k,n,vi,vj:integer;
min,mincost:real;
begin
vi:=0;
vj:=0;
read;
for i:=1 to ndo
for j:=1 to ndo
begin
read(v[i,j]);
if (v[i,j]=0)and(i<>j) then
v[i,j]:=maxint;
end;
fillchar(s,sizeof(s),0);
min:=maxint;
mincost:=0;
for i:=2 to ndo
for j:=1 to ido
if v[i,j]<min then
begin
min:=v[i,j];
vi:=i;
vj:=j;
end;
alv[1]:=vi;
alv[2]:=vj;
s[vi]:=true;
s[vj]:=true;
writeln(vi,vj);
mincost:=mincost+v[vi,vj];
k:=3;
while(k<=n)do
begin
min:=maxint;
for i:=1 to ndo
begin
if s then
continue;
for j:=1 to k-1do

begin
if v[i,alv[j]]<min then
begin
min:=v[i,alv[j]];
vi:=i;
vj:=alv[j];
end;
end;
end;
alv[k]:=vi;
s[vi]:=true;
writeln(vi,vj);
mincost:=mincost+v[vi,vj];
k:=k+1;
end;

writeln(mincost);
end.

這個題目好像還有種算法，就是先排好序再進行連

多人接受答案了。