讨论 / 求神牛指点错误。。。
cqw 2012-08-21 23:54:00
点我顶贴 收藏 删除
WA:40

var

a, b, c : array[1..100003] of longint;

f, s : array[1..20003] of longint;

n, m, sa, sb : longint;

procedure init;

var i:longint;

begin

readln(n, m);

for i:=1 to m do readln(a[i], b[i], c[i]);

end;

procedure qs(l, r:longint);

var i, j, mid, temp:Longint;

begin

i:=l;

j:=r;

mid:=c[(l+r) div 2];

repeat

while c[i]<mid do inc(i);

while c[j]>mid do dec(j);

if i<=j then begin

temp:=a[i];a[i]:=a[j];a[j]:=temp;

temp:=b[i];b[i]:=b[j];b[j]:=temp;

temp:=c[i];c[i]:=c[j];c[j]:=temp;

inc(i);dec(j);

end;

until i>j;

if i<r then qs(i, r);

if j>l then qs(l, j);

end;

function getfather(x:longint):longint;

begin

while x<>f[x] do x:=f[x];

exit(x);

end;

procedure union(x, y:longint);

begin

f[x]:=y;

end;

procedure correct(x:longint);

begin

if x<>f[x] then begin

correct(f[x]);

s[x]:=(s[f[x]]+1) mod 2;

end

else exit;

end;

procedure main;

var i:longint;

begin

for i:=1 to n do begin

f[i]:=i;

s[i]:=0;

end;

qs(1, m);

for i:=m downto 1 do begin

sa:=getfather(a[i]);

sb:=getfather(b[i]);

if sa=sb then begin

if s[a[i]]=s[b[i]] then begin

write(c[i]);

exit;

end;

end

else begin

union(sa, sb);

correct(a[i]);

end;

end;

write(0);

end;

begin

init;

main;

end.

查看更多回复
提交回复