讨论 / 很诡异的题目
ergyioreya 2008-11-04 01:17:00
点我顶贴 收藏 删除
我没改一个字的程序交两次,竟然出现了两种评测结果

请管理员说明原因

#1 Zx.MYS@2008-09-28 07:40:00
回复 删除
哪不同了?

#2 ergyioreya@2008-09-29 04:10:00
回复 删除
我强烈要求管理员检查题目数据

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为什么改个类型就有分数区别?

不懂了?难道数据和题目有出入。

这样的题目怎能让人做。

#3 B-L-A-C-K@2008-11-04 01:17:00
回复 删除
我Prim

longint 90分

dword 80分

查看更多回复
提交回复