bzoj1854: [Scoi2010]游戏【并查集】

  • 内容
  • 评论
  • 相关

高产模式启动~(虽然也不会高产到哪里去)


题目点击这里

这题是用的一个神奇的并查集的方法来做的,转化地很巧妙,并且比较容易理解,反正如果比赛出这个我是想不到的吧。。。

我们可以对每一个属性建一个点,把每个装备视为一个连接两个对应属性的点的无向边,那么建完图后我们会发现会出现一个个联通块。由于题意我们可以想到如果一个联通块是一个环,那么这个环上所有的属性都是可以使用一次的。如果是一棵树,那么这棵树上有且只有一个属性是不能用的。

然后可以考虑用并查集来乱搞,然后再用一个vis数组记录每个属性能否使用。

首先对于一个联通块来说,这个联通块的祖先要求是在整个块中编号最大的点(如果想不明白先看完这一段)。当我们添加一条边时,如果这条边是在同一个联通块里面的,那么这个联通块肯定就会出现一个环,那么显然这个联通块中所有的属性都可以使用。如果连接的是两个联通块,那么一定是产生一棵新的树,编号较小的节点的属性也就可以使用了,而为了题意,我们就将编号较大的节点作为较小的节点的父亲。

最后由于我们在合并的时候记录下了每种属性是否可以使用,那么只要从小到大找到第一个无法使用的属性就可以了。

代码:

var
  f:array[1..10000]of longint;
  vis:array[1..10001] of boolean;
  n,m,i,j,k,p,q:longint;
function gf(x:longint):longint;
begin
  if f[x]=0 then exit(x)
  else f[x]:=gf(f[x]);
  exit(f[x]);
end;
procedure union(x,y:longint);
var
  p,q:longint;
begin
  p:=gf(x);
  q:=gf(y);
  if p=q then
  begin
    vis[p]:=true;
    exit;
  end;
  if p<q then
  begin
    vis[p]:=true;
    f[p]:=q;
  end;
  if p>q then
  begin
    vis[q]:=true;
    f[q]:=p;
  end;
end;
begin
  read(n);
  fillchar(vis,sizeof(vis),false);
  for i:=1 to n do
  begin
    read(p,q);
    union(p,q);
  end;
  for i:=0 to 10000 do
  if not vis[i+1] then
  begin
    writeln(i);
    break;
  end;
end.

退役倒计时:25天

评论

0条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据