下面的离答案总差一点
求解！！！
program prim_yan;
var i,j,n,m,k,t,tot,mj,min:longint;
d:array[1..10000]of longint;
map,chart:array[1..100,1..100]of longint;
first,lowcost:array[1..100]of longint;
flag:array[1..100]of boolean;
procedure heap(nn,xi:longint);
var i1,j1,xx:longint;
begin
xx:=d[xi];
i1:=xi;j1:=2*xi;
while j1<=nn do
begin
if (j1<n)and(lowcost[d[j1]]>lowcost[d[j1+1]]) then j1:=j1+1;
if lowcost[xx]>lowcost[d[j1]] then
begin
d[i1]:=d[j1];i1:=j1;j1:=i1*2;
end
else j1:=nn+1;
end;
d[i1]:=xx;
end;
procedure insert(xi,yi:longint);
var i1,j1,xx:longint;
begin
d[t]:=yi;i1:=t;j1:=i1 div 2;
while j1>=1 do
begin
if lowcost[d[j1]]>lowcost[yi] then
begin
i1:=j1;j1:=i1 div 2;
end
else j1:=0;
end;
d[i1]:=yi;
end;
begin
assign(input,'hpny.in');
reset(input);
assign(output,'hpny.out');
rewrite(output);
readln(n);
fillchar(first,sizeof(first),0);
fillchar(lowcost,sizeof(lowcost),$5F);
for i:=1 to n do
begin
for j:=1 to n do
begin
read(map[i,j]);
if i<>j then
begin
inc(first[i]);chart[i,first[i]]:=j;
end;
end;
readln;
end;
t:=0;fillchar(flag,sizeof(flag),false);
lowcost[1]:=0;flag[1]:=true;
for i:=1 to first[i] do
begin
lowcost[chart[1,i]]:=map[1,chart[1,i]];
inc(t);
insert(1,chart[1,i]);
end;
for i:=2 to n do
begin
while flag[d[1]]=true do
begin
d[1]:=d[t];dec(t);
heap(t,1);
end;
flag[d[1]]:=true;mj:=d[1];
inc(tot,lowcost[mj]);
d[1]:=d[t];dec(t);
heap(t,1);
for j:=1 to first[mj] do
begin
if (not flag[chart[mj,j]])and(lowcost[chart[mj,j]]>map[mj,chart[mj,j]]) then
begin
lowcost[chart[mj,j]]:=map[mj,chart[mj,j]];
inc(t);
insert(mj,chart[mj,j]);
end;
end;
end;
writeln(tot);
close(input);close(output);
end.
本人找不出来那里的问题
只是想试一下优化，结果悲惨失败
对比一下不优化的
program hapy;
var
d:array[1..1000]of longint;
chart:array[1..1000]of boolean;
i,j,min,n,ans,k:longint;
w:array[1..1000,1..1000]of longint;
begin
fillchar(chart,sizeof(chart),false);
readln(n);
for i:=1 to n do
for j:=1 to n do
read(w[i,j]);
for i:=2 to n do d[i]:=maxlongint;
d[1]:=0;ans:=0;
for i:=1 to n do
begin
min:=maxlongint;
for j:=1 to n do
if not chart[j] and (d[j]<min) then begin k:=j;min:=d[j];end;
if min=maxlongint then begin ans:=-1;break;end;
ans:=ans+min;chart[k]:=true;
for j:=1 to n do
if w[k,j]<d[j] then d[j]:=w[k,j];
end;
writeln(ans);
readln;readln;
end.