爱华网2011.7.23 22:32
呵呵,会了NOIP2010第三题的第二种方法了,不过总体思路差不多，都是根据怨气值为总体思路,只不
过判断是否在监狱的工具不同了,新学的这个是用并查集做。
说下思路，先是把怨气值从小到大排序一遍，然后从大到小枚举，然后对于每个关系进行判断，需
要新开一个数组h[i]，表示i的敌人是h[i],然后如果两个人都没有敌人就想让这个怨气值取消不存在，就
让这两个人互为敌人，然后如果两个人其中一人或两人都有敌人就没敌人的那个人把对方当成敌人，然 后
合并两个并查集，让y和x的敌人的并查集合并，让x和y的敌人的并查集合并。如果两个人在同一并查集中
，就说明之前他俩已经分一个监狱了，这个怨气值满足，那么就输出这个怨气值好了。
本题犯了一个重大错误，在合并的时候只考虑其中一方没敌人，而没考虑两个人都有敌人，把union
写到了标记敌人的嵌套里了，重大错误！！！
代码：
type
bian=record
x,y,d:longint;
end;
//==============================================================================
var
f:Array[0..20000] of longint;
h:array[0..20000] of longint;
map:array[0..100000] of bian;
n,m:longint;
//==============================================================================
procedure qsort(l,r:longint);
var
i,j,mid:longint;
t:bian;
begin
i:=l;
j:=r;
mid:=map[(l+r) div 2].d;
repeat
whilemap[i].d>mid do inc(i);
whilemap[j].d<mid do dec(j);
ifi<=j then
begin
t:=map[i];
map[i]:=map[j];
map[j]:=t;
inc(i);
dec(j);
end;
until i>j;
if i<r then qsort(i,r);
if l<j then qsort(l,j);
end;
//==============================================================================
procedure init;
var
i:longint;
begin
readln(n,m);
fillchar(h,sizeof(h),0);
for i:=1 to m do
readln(map[i].x,map[i].y,map[i].d);
for i:=1 to n do
f[i]:=i;
qsort(1,m);
// for i:=1 to m do
//writeln(map[i].d);
end;
//==============================================================================
function get(t:longint):longint;
begin
if f[t]=t then exit(t);
f[t]:=get(f[t]);
exit(f[t]);
end;
//==============================================================================
procedure union(t1,t2:longint);
var
xx,yy:longint;
begin
xx:=get(t1);
yy:=get(t2);
if xx<>yy thenf[xx]:=yy;
end;
//==============================================================================
procedure main;
var
tx,ty,i,j:longint;
begin
for i:=1 to m do
begin
tx:=get(map[i].x);
ty:=get(map[i].y);
if tx=ty then{如果同为一个监狱（并查集）}
begin
writeln(map[i].d);
close(input);
close(output);
halt;
end;
if (h[map[i].x]=0) and (h[map[i].y]=0) then{如果都没有敌人就互为敌人}
begin
h[map[i].x]:=map[i].y;
h[map[i].y]:=map[i].x;
continue;
end;
if h[map[i].x]=0 then{如果x没敌人，就把y当x的敌人}
begin
h[map[i].x]:=map[i].y;
end;
if h[map[i].y]=0 then{如果y没敌人，就把x当y的敌人}
begin
h[map[i].y]:=map[i].x;
end;
union(h[map[i].x],map[i].y);{合并两个并查集}
union(h[map[i].y],map[i].x);
end;
writeln(0);
end;
//==============================================================================
begin
assign(input,'prison.in'); reset(input);
assign(output,'prison.out');rewrite(output);
init;
main;
close(input); close(output);
end.
