求二叉堆优化过的Prim代码

用二叉堆实现优先队列么 不如学白书priority_queue

朴素的就挺好啊。。稀疏图用kruskal

。。。丢两个模板上来您自己选吧
const maxn=200000;
maxe=200000;
type edge=record
a,b:longint;
len:int64;
end;
type arr=record
x,y,z:longint;
end;
var edges:array[0..maxe]of edge;
p,r,check:array[0..maxn]of int64;
heart:array [0..maxn] of arr;
n,e:longint;
procedure swap(a,b:longint);
begin
edges[0]:=edges[a];
edges[a]:=edges[b];
edges[b]:=edges[0];
end;
procedure qsort(l,r:longint);
var x,i,j:longint;
begin
x:=edges[random(r-l+1)+l].len;
i:=l;j:=r;
repeat
while edges[i].len<x do inc(i);
while edges[j].len>x do dec(j);
if i<=j then
begin
swap(i,j);
inc(i);dec(j);
end
until i>j;
if l<j then qsort(l,j);
if i<r then qsort(i,r);
end;
function min(x,y:int64):int64;
begin
if x<y then exit(x)
else exit(y);
end;
procedure init;
var i,j:longint;
begin
readln(n,e);
for i:=1 to e do read(edges[i].a,edges[i].b,edges[i].len);
for i:=1 to n do p[i]:=i;
randomize;
end;
function find(i:longint):longint;
begin
if p[i]=i then exit(i);
if p[p[i]]=0 then exit(p[i]);
find:=find(p[i]);
p[i]:=find;
end;
procedure union(a,b:longint);
var t:longint;
begin
a:=find(a);
b:=find(b);
if r[a]>r[b] then begin t:=a;a:=b;b:=t end;
if r[a]=r[b]then inc(r[a]);
p[a]:=b;
end;
procedure kruskal;
var en:longint;
count,xx,yy:longint;
tot,ans:int64;
begin
count:=0; en:=0; tot:=0; ans:=maxlongint;
while count<n-1 do
begin
inc(en);
with edges[en] do
begin
if find(a)<>find(b) then
begin
union(a,b);
inc(tot,len);
inc(count);
end;
end;
end;
writeln(tot);
end;
begin
init;
kruskal;
end.
上面是kruskal+ufs的
type node=record
x,y,next:longint;
end;
var pos,closest,lowest,heap:array [1..100] of longint;
a:array [1..100,1..100] of longint;
v:array [1..100] of boolean;
tot,n,ans:longint;
function init:boolean;
var i,j,x,y,z:longint;
begin
read(n);
for i:=1 to n do
begin
read(x,y,z);
if a[x,y]=0 then
begin
a[x,y]:=z;
a[y,x]:=z;
end
else
if a[x,y]>z then
begin
a[x,y]:=z;
a[y,x]:=z;
end;
end;
exit(true);
end;
procedure swap(var i,j:longint);
var t:longint;
begin
t:=i;
i:=j;
j:=t;
end;
procedure down(l:longint);
begin
while l*2<=tot do
begin
l:=l*2;
if l<tot then
if lowest[heap[l]]>lowest[heap[l+1]] then inc(l);
if lowest[heap[l]]>=lowest[heap[l div 2]] then exit;
swap(pos[heap[l]],pos[heap[l div 2]]);
swap(heap[l],heap[l div 2]);
end;
end;
procedure up(l:longint);
begin
while l>1 do
begin
if lowest[heap[l]]>=lowest[heap[l div 2]] then exit;
swap(pos[heap[l]],pos[heap[l div 2]]);
swap(heap[l],heap[l div 2]);
l:=l div 2;
end;
end;
procedure make_heap;
var i,j:longint;
begin
for i:=1 to n do
begin
heap[i]:=i;
pos[i]:=i;
end;
for i:=1 to n do
begin
lowest[i]:=a[1,i];
up(pos[i]);
end;
end;
procedure heap_prim;
var i,j,k:longint;
begin
tot:=n;
fillchar(v,sizeof(v),true);
v[1]:=false;
for i:=1 to n-1 do
begin
k:=heap[1];
swap(pos[heap[1]],pos[heap[tot]]);
swap(heap[1],heap[tot]);
dec(tot);
inc(ans,lowest[k]);
lowest[k]:=maxlongint;
v[k]:=false;
down(1);
for j:=1 to n do
if (a[k,j]<lowest[j]) and v[j] then
begin
lowest[j]:=a[k,j];
up(pos[j]);
end;
end;
writeln(ans);
end;
begin
while init do
begin
make_heap;
heap_prim;
end;
end.
prim+heap