type dd=record
x,y,w:longint;
end;
var i,j,n,m,k,t,total,mj,min:longint;
d:array[1..10000]of dd;
map,chart:array[1..100,1..100]of longint;
first,lowcost:array[1..100]of longint;
flag:array[1..100]of boolean;
procedure heap(tt,ii:longint);
var i1,j1,xx,xi,yi:longint;
begin
xx:=d[ii].w;xi:=d[ii].x;yi:=d[ii].y;
i1:=ii;j1:=ii*2;
while j1<=tt do
begin
if (j1<tt)and(d[j1].w>d[j1+1].w) then j1:=j1+1;
if xx>d[j1].w then
begin
d[i1].x:=d[j1].x;d[i1].y:=d[j1].y;d[i1].w:=d[j1].w;
i1:=j1;j1:=j1*2;
end
else j1:=tt+1;
end;
d[i1].x:=xi;d[i1].y:=yi;d[i1].w:=xx;
end;
procedure insert(xi,yi:longint);
var xx,j1,i1:longint;
begin
d[t].x:=xi;d[t].y:=yi;d[t].w:=map[xi,yi];xx:=map[xi,yi];
j1:=t div 2;i1:=t;
while j1>=1 do
begin
if (j1>1)and(d[j1].w>d[j1+1].w) then j1:=j1+1;
if xx<d[j1].w then
begin
d[i1].x:=d[j1].x;d[i1].y:=d[j1].y;d[i1].w:=d[j1].w;
i1:=j1;j1:=j1 div 2;
end
else j1:=0;
end;
d[i1].x:=xi;d[i1].y:=yi;d[i1].w:=xx;
end;
begin
readln(n);
fillchar(first,sizeof(first),0);
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);
for i:=2 to n do lowcost[i]:=maxlongint;
lowcost[1]:=0;
for i:=1 to first[1] do
begin
inc(t);
insert(1,chart[1,i]);
end;
flag[1]:=true;
for i:=2 to n do
begin
while flag[d[1].y]=true do
begin
d[1].x:=d[t].x;d[1].y:=d[t].y;d[1].w:=d[t].w;dec(t);
heap(t,1);
end;
lowcost[d[1].y]:=d[1].w;mj:=d[1].y;
min:=d[1].w;
flag[mj]:=true;inc(total,min);
d[1].x:=d[t].x;d[1].y:=d[t].y;d[1].w:=d[t].w;dec(t);
heap(t,1);
for j:=1 to first[mj] do
if flag[chart[mj,j]]=false and(lowcost[chart[mj,j]]>map[mj,chart[mj,j]]) then
begin
inc(t);
insert(mj,chart[mj,j]);
end;
end;
writeln(total);
end.
上面是错的我知道了
下面的离答案总差一点
求解！！！
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.