ACM--ICPC--重要补充知识

《ACM--ICPC--重要补充知识》由会员分享，可在线阅读，更多相关《ACM--ICPC--重要补充知识（13页珍藏版）》请在装配图网上搜索。

1、word在一些有N个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。这一类问题近几年来反复出现在信息学的国际国内赛题中，其特点是看似并不复杂，但数据量极大，假如用正常的数据结构来描述的话，往往在空间上过大，计算机无法承受；即使在空间上勉强通过，运行的时间复杂度也极高，根本就不可能在比赛规定的运行时间13秒内计算出试题需要的结果，只能采用一种全新的抽象的特殊数据结构并查集来描述。什么是并查集？并查集是一种树型的数据结构，用于处理一些不相交集合Disjoint Sets的合并与查询问题。常常

2、在使用中以森林来表示。集就是让每个元素构成一个单元素的集合，并就是按一定顺序将属于同一组的元素所在的集合合并。编辑本段并查集的主要操作：初始化把每个点所在集合初始化为其自身查找查找元素所在的集合即根节点合并将两个元素所在的集合合并为一个集合合并两个不相交集合判断两个元素是否属于同一集合辅助例题亲戚(Relations)题目描述： 假如某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现在给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。规定：x和y是亲戚，y和z是亲戚，那么x和z也是亲戚。如果x,y是亲戚，那么x的亲戚都是y的亲戚，y的亲戚也都是x的亲戚。 输入格式 Input

3、 Format 第一行：三个整数n,m,p，n=5000,m=5000,p=5000，分别表示有n个人，m个亲戚关系，询问p对亲戚关系。以下m行：每行两个数Mi，Mj，1=Mi，Mjrank28 then pa29 else pab30 if ranka=rank31 then rankrank+1然而算法的耗时主要还是花在SUB-Find-Set(x)上。第二个优化是路径压缩。它非常简单而有效。如下列图，在SUB-Find-Set(1)时，我们“顺便将节点1, 2, 3的父节点权改为节点4，以后再调用SUB-Find-Set(1)时就只需O(1)的时间。图0-0-4于是SUB-Find-Se

4、t(x)的代码改为：SUB-Find-Set(x)32 if x?px33 then pxSUB-Find-Set(px)34 return px该过程首先找到树的根，然后将路径上的所有节点的父节点改为这个根。实现时，递归的程序有许多栈的操作，改成非递归会更快些。SUB-Find-Set(x)35 rx36 while r?pr37 do rpr38 while x?r39 do qpx40 pxr41 xq42 return r改良后的算法时间复杂度的分析十分复杂，如果完整的写出来足可写一节，这里我们指给出结论：改良后的PROBLEM-Relations其时间复杂度为O(N+(M+Q)?(M

5、+Q,N)，其中?(M+Q,N)为Ackerman函数的增长极为缓慢的逆函数。你不必了解与Ackerman函数相关的内容，只需知道在任何可想象得到的别离集合数据结构的应用中，?(M+Q,N) ? 4，因此PROBLEM-Relations的时间复杂度可认为是线性的O(N+M+Q)。解(略)编辑本段总述此题的输入数据量很大，这使得我们的程序会在输入中花去不少时间。如果你用Pascal写程序，可以用库函数SetTextBuf为输入文件设置缓冲区，这可以使输入过程加快不少。如果你是用C语言的话，就不必为此操心了，系统会自动分配缓冲区。并查集学习小节(POJ版)什么是并查集呢，我相信大家都已经很熟悉了

6、，在这里我就不再赘述。写这篇文章的主要目的不是新手教学，而是为了借POJ上相关的题目，全面的总结一下并查集问题和它的各个变种。POJ 1611 The Suspects题目大意:有n个学生标号为0 to n-1),m个学生社团，给出每个社团里所有学生的标号，并假设0号学生患有SARS社团里只要用一个学生患病，如此整个社团里的学生都会被隔离，问最后一共会有多少学生被隔离？这是一个最根底的并查集的应用，扫描每一个社团，只要两个学生出现在同一个社团，如此将这两个集合合并起来，最后输出0号点所在集合的rank值集合rank值记录这个集合中的元素个数并用一个flag值跟踪0号元素所在集合标号即可。这是并

7、查集问题的第一种应用：集合合并，判断两点是不是在同一个集合，求某一个集合上的元素个数等。#include#defineMAX30000intfMAX;/这里的1001只是一个示意性的数字代表初始状态下的分支数目intrMAX;intflag;/由于不知道应该将子树挂到那个集合上面去，故需要一个准如此，这里的准如此是将子树挂到/r值大的集合上面去,初始状态下r数组的值均为一，代表每个分支下只有一个数字intfind(intn)if(fn=n)returnn;elsefn=find(fn);returnfn;/查找函数，并压缩路径intUnion(intx,inty)inta=find(x);in

8、tb=find(y);if(a=b)return0;elseif(ra=rb)fa=b;rb+=ra;if(a=flag)flag=b;elsefb=a;ra+=rb;if(b=flag)flag=a;return1;/合并函数，如果属于同一分支如此返回0，成功合并返回1intmain()intn,m;inti,j;intnum;intmaxnum=0;while(scanf(%d%d,&n,&m)flag=0;maxnum=0;inttemp1,temp2;if(n=0&m=0)break;for(i=0;in;i+)fi=i;ri=1;for(j=1;j=m;j+)scanf(%d,&nu

9、m);for(i=0;inum;i+)if(i=0)scanf(%d,&temp1);elsescanf(%d,&temp2);Union(temp1,temp2);printf(%dn,rflag);return0;HDOJ1213 How many tables?#include #include #include #define MAX 30000 using namespace std; int fMAX; int rMAX; int flag; int find(int n) if(fn!=n) fn=find(fn); return fn; int Union(int x,int

10、y) int a=find(x); int b=find(y); if(a=b) return 0; else fa=b; return 1; int main() int n,m; int i,j; int num,N; int maxnum=0;scanf(%d,&N); while(N!=0) N-; scanf(%d%d,&n,&m); int temp1,temp2; for(i=1;i=n;i+) fi=i; ri=1; for(j=1;jtemp1temp2; Union(temp1,temp2); int sum=0; for(j=1;j=n;j+) if(fj=j) sum+

11、; coutsum首先1,2是异性。-然后2,3是异性。可以推出1,3是异性。但是1，3有性行为，所以可以判断出有一定有同性恋。剥离这个题目所赋予的外壳，我们抽出这个问题的本质：并查集！其实，这里最重要的是去维护每一个点到集合顶点的偏移量。注意：下面生造了一个词 所谓集合元素 比如说fi=i,那么i就是集合元素，集合偏移量就是集合元素的偏移量初始状态下，应该是 i号点挂在i号集合下面我们考虑一般情况：假设合并的过程已经进展了一局部 ，这样每一个集合下面都有元素，且各自对于顶点的偏移量都算出来了；现在在a集合中的元素x和b集合中的元素y进展合并。此时有两中情况改变偏移量；1.首先是集合的合并，如

12、果要将a,b集合合并，又要保证x,y数字的kind不一样，比如说把b集合挂到a集合下面去。代表集合的那个元素，他的偏移量永远是0，所以b要改变偏移量，使得b里面的y在进展变换后要和x相异。如果 kindx=0;kindy=0;那么y对应的那个代表集合的元素的偏移量必须变成1，因为只有这样才能使得合并后，x,y有不同的kind;如果 kindx=0,kindy=1;y对应代表集合的元素偏移量是0，所以对应集合偏移量还是0；类推kindx=1,kindy=0,同上,0；kindx=1,kindy=1,y集合偏移量应该变为1；综上 可以得到一个同或的关系。用等式kinda=(kindx+kindy个

13、人认为，这个主要是解决集合合并时候产生的“剩余问题，因为在合并集合的时候只是考虑了集合的偏移量，至于它下面的元素一概不管。一个压缩路径既别离了父子元素的偏移量，又使得子元素直接指向集合元素。总而言之，并查集的操作就是不断地维护者各个集合中，每个元素身上对集合元素的偏移关系。从而确定他们是否具有同性恋。在这个题中，假设是不存在同性恋的，所以只有找到矛盾才输出 有同性恋。#include#includeusingnamespacestd;#defineMAX2001intfMAX;intkindMAX;intn,m;inttestcase;voidinit()inti;for(i=1;i=n;i+

14、)fi=i;kindi=0;intFind(intn)if(fn=n)returnn;intt=Find(fn);kindn=(kindn+kindfn)%2;fn=t;returnfn;intUnion(intx,inty)inta=Find(x);intb=Find(y);if(a=b)if(kindx=kindy)return1;/1代表有同性恋情况elsefa=b;kinda=(kindx+kindy+1)%2;return0;intmain()scanf(%d,&testcase);inti,j;inta,b;intflag;for(i=1;i=testcase;i+)flag=0;

15、scanf(%d%d,&n,&m);init();for(j=1;j=m;j+)scanf(%d%d,&a,&b);if(Union(a,b)flag=1;if(flag=1)printf(Scenario#%d:nSuspiciousbugsfound!nn,i);elseprintf(Scenario#%d:nNosuspiciousbugsfound!nn,i);return0;POJ 1182食物链中文题，让你输出假话的个数。其实这道题是上一道题的扩展，如果把上一道题也想成是食物链的话，就是1吃2，2吃1.而这里是三个动物，所以同样是维护一个偏移量，只不过多了一位罢了。程序的过程实质上

16、就是在维护并查集，判断是否是假话是在维护的过程中进展的，只能算是附属品吧。#includeusingnamespacestd;#defineMAX50005intfMAX;intkindMAX;intn,m;voidinit()inti;for(i=1;in|yn)return1;inta=Find(x);intb=Find(y);if(c=1)if(a=b)if(kindx!=kindy)returntrue;elseif(a!=b)fb=a;kindb=(kindx-kindy+3)%3;elseif(x=y)returntrue;if(a=b)if(kindx+1)%3!=kindy)r

17、eturntrue;elseif(a!=b)fb=a;kindb=(kindx-kindy+4)%3;returnfalse;intmain()inti,j;inta,b,c;intsum=0;scanf(%d%d,&n,&m);init();for(i=1;i=m;i+)scanf(%d%d%d,&c,&a,&b);if(Union(a,b,c)sum+;printf(%dn,sum);return0;这里将两个集合并起来并将所挂集合偏移量指向：kindb=(kindx-kindy+4)%3;想想上一题是不是也很类似呢其实上一题的公式也可以改成kindb=(kindx-kindy+3)%2;

18、 不管是几个动物循环，都能得到类似的结论，所以以后碰到4，5，6，7。个动物的食物链，你应该也会做了吧？_POJ 1988 Cube Stacking这道题更有意思了，说它开辟了并查集问题的新局面并不为过；上面2道题，研究的主要是到集合元素的偏移量，而这道题要求的是一个“逻辑上到达集合元素的距离！集合合并的时候同样只修改被挂集合元素的距离值，剩余局部留给压缩路径来处理.如果理解了上面的问题，这个问题就很好理解了。#include#include#includeusingnamespacestd;#defineMAX30000intfMAX+1;intrMAX+1;intaboveMAX+1;v

19、oidinit()inti;for(i=1;i=MAX;i+)abovei=0;fi=i;ri=1;intrealfather;intfind(intn)intt;if(fn=n)realfather=n;returnn;elset=find(fn);if(fn!=realfather)aboven+=(abovefn);fn=t;returnfn;/查找函数，并压缩路径voidUnion(intx,inty)inta=find(x);intb=find(y);fb=a;aboveb+=ra;ra+=rb;/合并函数，如果属于同一分支如此返回0，成功合并返回1intmain()intp;inti;init();charorder;inta,b;scanf(%d,&p);for(i=1;i=p;i+)cin.ignore();scanf(%c,&order);if(order=M)scanf(%d%d,&a,&b);Union(a,b);elseif(order=C)scanf(%d,&a);printf(%dn,rfind(a)-abovea-1);return0;银河英雄传说 NOI 2002文档