测试结果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.
非常丑陋的快排和并查集 但为什么会错呢
大牛指点下吧
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.
这个也不对 为什么啊 求神牛解释……………………
状态: 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;
}
}
}
同求高手指教,是不是不仅要用并查集看两点是否有关系,还要看是否在同一监狱??