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天
发表回复