NOIP2010关押罪犯并查集方法 noip关押罪犯

2011.7.23 22:32

呵呵,会了NOIP2010第三题的第二种方法了,不过总体思路差不多,都是根据怨气值为总体思路,只不

过判断是否在监狱的工具不同了,新学的这个是用并查集做。
说下思路,先是把怨气值从小到大排序一遍,然后从大到小枚举,然后对于每个关系进行判断,需

要新开一个数组h[i],表示i的敌人是h[i],然后如果两个人都没有敌人就想让这个怨气值取消不存在,就

让这两个人互为敌人,然后如果两个人其中一人或两人都有敌人就没敌人的那个人把对方当成敌人,然 后

合并两个并查集,让y和x的敌人的并查集合并,让x和y的敌人的并查集合并。如果两个人在同一并查集中

,就说明之前他俩已经分一个监狱了,这个怨气值满足,那么就输出这个怨气值好了。

本题犯了一个重大错误,在合并的时候只考虑其中一方没敌人,而没考虑两个人都有敌人,把union

写到了标记敌人的嵌套里了,重大错误!!!

代码:

type
bian=record
NOIP2010关押罪犯并查集方法 noip关押罪犯
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.

  

爱华网本文地址 » http://www.aihuau.com/a/25101016/313618.html

更多阅读

农业银行怎么在手机上查余额 农业银行手机查询余额

农业银行怎么在手机上查余额——简介一般查询银行卡余额都是在ATM机,柜台,或者网上营业厅,那么怎么使用手机查询余额呢,下面就教大家查询方法。农业银行怎么在手机上查余额——方法1农业银行怎么在手机上查余额 1、使用手机拨打农业银

电信怎么查套餐 电信怎么查在用套餐

电信怎么查套餐——简介电信手机怎么查询套餐以及套餐的使用情况,目前大家可以通过四种自助方式查询电信手机的套餐以及套餐使用情况,主要是以下四种方法,分别是拨打电信客服电话自助查询、短信指令查询、掌上营业厅查询、电脑网上营业

怎么样才能获得PUK码并解锁 输入puk码解锁sim卡

怎么样才能获得PUK码并解锁——简介PUK码是什么?PUK码是用来解锁手机SIM卡的密码。而SIM卡密码为了保护SIM卡被泄露,而设定的一个密码(即PIN码)当这个密码输入三次错误就需要PUK码来解,而且在未解开之前SIM手机卡将不能使用。下面和大

如何进行市场调研? 如何做市场调研报告

? ? 市场调研是企业或政府获取信息的重要手段。随着经济的不断发展,市场调研对企业或地方政府的发展以及整个经济的作用也越来越大。市场调研的概念? ??所谓市场调研,是以系统的科学方法(如抽样设计等)搜集市场资料,并运用统计方法分

paperpass查重 paperpass充值中心

paperpass查重——简介毕业论文撰写完毕,在让导师进行审阅之前需要对文章进行查重处理,查重可以基本限制你的论文抄袭率,降低你论文和别人论文的重复率,在一定程度上确保了论文的质量,当然,论文质量还是要看实质内容的,不是查重率低就能表

声明:《NOIP2010关押罪犯并查集方法 noip关押罪犯》为网友重新来过分享!如侵犯到您的合法权益请联系我们删除