讨论 / 求高手指教为何错
wjltz 2012-06-15 02:08:00
点我顶贴 收藏 删除
测试结果1: 通过本测试点|有效耗时157ms

测试结果2: 通过本测试点|有效耗时46ms

测试结果3: 测试结果错误.错误结果为:26865

正确结果应为:25120

测试结果4: 通过本测试点|有效耗时172ms

测试结果5: 通过本测试点|有效耗时171ms

测试结果6: 通过本测试点|有效耗时204ms

测试结果7: 通过本测试点|有效耗时500ms

测试结果8: 测试结果错误.错误结果为:31238

正确结果应为:30953

测试结果9: 测试结果错误.错误结果为:31191

正确结果应为:31065

测试结果10: 测试结果错误.错误结果为:29783

正确结果应为:29711

01.program lt1;

02.var

03.n,m,i,j,t:longint;

04.a:array[1..20000] of longint;

05.x1,y1,b:array[1..100000] of longint;

06.function zhaodie(x:longint):longint;

07.var t:longint;

08.begin

09.

t:=x;

10.

while a[t]<>t do

11.

begin

12.

a[t]:=a[a[t]];

13.

t:=a[t];

14.

end;

15.

a[x]:=t;

16.

zhaodie:=t;

17.end;

18.procedure try(x,y:longint);

19.var l,r,t:longint;

20.begin

21.

if x>=y then exit;

22.

l:=x; r:=y;

23.

while l<r do

24.

begin

25.

t:=0;

26.

while (b[l]>=b[r]) and (l<r) do dec(r);

27.

t:=b[l];

28.

b[l]:=b[r];

29.

b[r]:=t;

30.

t:=x1[l];

31.

x1[l]:=x1[r];

32.

x1[r]:=t;

33.

t:=y1[l];

34.

y1[l]:=y1[r];

35.

y1[r]:=t;

36.

while (b[l]>=b[r]) and (l<r) do inc(l);

37.

t:=b[l];

38.

b[l]:=b[r];

39.

b[r]:=t;

40.

t:=x1[l];

41.

x1[l]:=x1[r];

42.

x1[r]:=t;

43.

t:=y1[l];

44.

y1[l]:=y1[r];

45.

y1[r]:=t;

46.

end;

47.

try(x,l-1);

48.

try(l+1,y);

49.end;

50.begin

51.

readln(n,m);

52.

for i:=1 to m do

53.

readln(x1[i],y1[i],b[i]);

54.

try(1,m);

55.

for i:=1 to n do

56.

a[i]:=i;

57.

for i:=1 to m do

58.

begin

59.

if zhaodie(x1[i])=zhaodie(y1[i]) then begin

60.

write(b[i]);

61.

halt;

62.

end;

63.

a[zhaodie(x1[i])]:=zhaodie(y1[i]);

64.

end;

65.

write(0);

66.end.

非常丑陋的快排和并查集 但为什么会错呢

大牛指点下吧

#1 wjltz@2011-06-23 02:26:00
回复 删除
program lt1;

var dr,c,f,a,b:array[1..50000] of longint;

n,m,i,j:longint;

function gf(x:longint):longint;

var d:longint;

begin

if x=c[x] then exit(x);

c[x]:=gf(c[x]);

exit(c[x]);

end;

procedure kp(x,y:longint);

var t,l,r:longint;

begin

if x>=y then exit;

l:=x;

r:=y;

while l<r do

begin

while (f[l]>=f[r]) and (l<r) do inc(l);

t:=f[l];

f[l]:=f[r];

f[r]:=t;

t:=a[l];

a[l]:=a[r];

a[r]:=t;

t:=b[l];

b[l]:=b[r];

b[r]:=t;

while (f[l]>=f[r]) and (l<r) do dec(r);

t:=f[l];

f[l]:=f[r];

f[r]:=t;

t:=a[l];

a[l]:=a[r];

a[r]:=t;

t:=b[l];

b[l]:=b[r];

b[r]:=t;

end;

kp(x,l-1);

kp(l+1,y);

end;

begin

fillchar(dr,sizeof(dr),0);

readln(n,m);

for i:=1 to m do

readln(a[i],b[i],f[i]);

for i:=1 to n do

c[i]:=i;

kp(1,m);

for i:=1 to m do

begin

if gf(a[i])=gf(b[i]) then begin

writeln(f[i]);

halt;

end;

if (dr[a[i]]<>0) and (dr[b[i]]=0) then begin

dr[gf(b[i])]:=gf(a[i]);

c[dr[gf(a[i])]]:=gf(b[i]);

continue;

end;

if (dr[b[i]]<>0) and (dr[a[i]]=0) then begin

dr[gf(a[i])]:=gf(b[i]);

c[dr[gf(b[i])]]:=gf(a[i]);

continue;

end;

if (dr[b[i]]<>0) and (dr[a[i]]<>0) then begin

c[dr[gf(b[i])]]:=gf(a[i]);

c[dr[gf(a[i])]]:=gf(b[i]);

continue;

end;

if (dr[a[i]]=0) and (dr[b[i]]=0) then begin

dr[a[i]]:=b[i];

dr[b[i]]:=a[i];

continue;

end;

end;

writeln(0);

end.

这个也不对 为什么啊 求神牛解释……………………

#2 12wang3@2011-09-10 03:31:00
回复 删除
无语,和我错的一模一样

状态: Unaccepted

测评机: Xeond[6]

得分: 60分

提交日期: 2011-9-10 17:46:00

有效耗时: 359毫秒

RQNOJ近期在线比赛列表

RQNOJ九月份月赛 时间:2011-9-24 18:30:00 [报名]

测试结果1: 通过本测试点|有效耗时47ms

测试结果2: 通过本测试点|有效耗时46ms

测试结果3: 测试结果错误.错误结果为:26865

正确结果应为:25120

测试结果4: 通过本测试点|有效耗时47ms

测试结果5: 通过本测试点|有效耗时47ms

测试结果6: 通过本测试点|有效耗时63ms

测试结果7: 通过本测试点|有效耗时109ms

测试结果8: 测试结果错误.错误结果为:31238

正确结果应为:30953

测试结果9: 测试结果错误.错误结果为:31191

正确结果应为:31065

测试结果10: 测试结果错误.错误结果为:29783

正确结果应为:29711

提交代码: view sourceprint?

#include<stdio.h>

int n,m,k;

int total;

int max;

long long spend;

struct node

{

int x,y,cost;

}f[200001];

int stu[200001];

int init_set()

{

int i;

for (i=1;i<=n;i++)

{

stu[i]=i;

}

}

int find_set(int x)

{

if (x!=stu[x])

{

stu[x]=find_set(stu[x]);

}

return stu[x];

}

int union_set(int x,int y)

{

int xl=find_set(x),yl=find_set(y);

if (xl!=yl)

{

total--;

stu[yl]=xl;

return 1;

}

return 0;

}

int quicksort(int l,int r)

{

int i=l,j=r,x=f[(l+r)/2].cost;

struct node s;

while (i<=j)

{

while (f[i].cost>x){i++;}

while (f[j].cost<x){j--;}

if (i<=j)

{

s=f[i];

f[i]=f[j];

f[j]=s;

i++;j--;

}

}

if (i<r){quicksort(i,r);}

if (j>l){quicksort(l,j);}

}

int main()

{

int i,j;

int sum;

scanf ("%d%d",&n,&m);

for (i=1;i<=m;i++)

{

scanf ("%d%d%d",&f[i].x,&f[i].y,&f[i].cost);

}

quicksort(1,m);

init_set();

for (i=1;i<=m;i++)

{

printf("<%d %d>=%d\n",f[i].x,f[i].y,f[i].cost);

if (union_set(f[i].x,f[i].y)==0)

{

printf("%d\n",f[i].cost);

//return 0;

}

}

}

同求高手指教,是不是不仅要用并查集看两点是否有关系,还要看是否在同一监狱??

#3 剪刀@2012-06-15 02:08:00
回复 删除
回复 楼主wjltz 的帖子

LZ 最后哪里错了,怎么AC的?

查看更多回复
提交回复