Const maxn=1000;
Type
rec=record x,y,a:longint; end;
Var
e:array[1..maxn*maxn] of rec;
father:array[0..maxn] of longint;
n,m,i:longint;
Procedure qsort(l,r:longint);
var
i,j,mid:longint;
tmp:rec;
begin
i:=l;j:=r;mid:=e[random(j-i)+i].a;
repeat
while e[i].a<mid do inc(i);
while e[j].a>mid do dec(j);
if i<=j then begin
tmp:=e[i];e[i]:=e[j];e[j]:=tmp;
inc(i);dec(j);
end;
until i>j;
if l<j then qsort(l,j);
if i<r then qsort(i,r);
end;
Function getfather(v:longint):longint;
begin
if father[v]=0 then getfather:=v else
getfather:=getfather(father[v]);
end;
Procedure choose;
var
ans,count,i:longint;
b:array[0..maxn] of boolean;
begin
fillchar(father,sizeof(father),0);
fillchar(b,sizeof(b),0);
count:=0;i:=1;
ans:=0;
while (count<>n-1) and (i<=m) do begin
if getfather(e[i].x)<>getfather(e[i].y) then begin
inc(count);
ans:=ans+e[i].a;
father[getfather(e[i].x)]:=getfather(e[i].y);
end;
inc(i);
end;
writeln(ans);
end;
Begin
readln(n,m);
for i:=1 to m do read(e[i].x,e[i].y,e[i].a);
qsort(1,m);
choose;
End.
kruskal+并查集 没有问题
但把答案改成int64的就70分,改成longint就80分
题目中明确说明A>0为什么改个类型就有分数区别?
不懂了?难道数据和题目有出入。
这样的题目怎能让人做。