愛(ài)華網(wǎng)2011.7.23 22:32
呵呵,會(huì)了NOIP2010第三題的第二種方法了,不過(guò)總體思路差不多，都是根據(jù)怨氣值為總體思路,只不
過(guò)判斷是否在監(jiān)獄的工具不同了,新學(xué)的這個(gè)是用并查集做。
說(shuō)下思路，先是把怨氣值從小到大排序一遍，然后從大到小枚舉，然后對(duì)于每個(gè)關(guān)系進(jìn)行判斷，需
要新開(kāi)一個(gè)數(shù)組h[i]，表示i的敵人是h[i],然后如果兩個(gè)人都沒(méi)有敵人就想讓這個(gè)怨氣值取消不存在，就
讓這兩個(gè)人互為敵人，然后如果兩個(gè)人其中一人或兩人都有敵人就沒(méi)敵人的那個(gè)人把對(duì)方當(dāng)成敵人，然 后
合并兩個(gè)并查集，讓y和x的敵人的并查集合并，讓x和y的敵人的并查集合并。如果兩個(gè)人在同一并查集中
，就說(shuō)明之前他倆已經(jīng)分一個(gè)監(jiān)獄了，這個(gè)怨氣值滿足，那么就輸出這個(gè)怨氣值好了。
本題犯了一個(gè)重大錯(cuò)誤，在合并的時(shí)候只考慮其中一方?jīng)]敵人，而沒(méi)考慮兩個(gè)人都有敵人，把union
寫(xiě)到了標(biāo)記敵人的嵌套里了，重大錯(cuò)誤！?。?/p>
代碼：
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{如果同為一個(gè)監(jiān)獄（并查集）}
begin
writeln(map[i].d);
close(input);
close(output);
halt;
end;
if (h[map[i].x]=0) and (h[map[i].y]=0) then{如果都沒(méi)有敵人就互為敵人}
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沒(méi)敵人，就把y當(dāng)x的敵人}
begin
h[map[i].x]:=map[i].y;
end;
if h[map[i].y]=0 then{如果y沒(méi)敵人，就把x當(dāng)y的敵人}
begin
h[map[i].y]:=map[i].x;
end;
union(h[map[i].x],map[i].y);{合并兩個(gè)并查集}
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.
愛(ài)華網(wǎng)本文地址 » http://www.klfzs.com/a/25101016/313618.html
