Skip to content

Tag Archives: 算法

求最大流的使用距离标号的最短增广路算法

求最大流有一种经典的算法,就是每次找增广路时用BFS找,保证找到的增广路是弧数最少的,也就是所谓的Edmonds-Karp算法。可以证明的是在使用最短路增广时增广过程不超过V*E次,每次BFS的时间都是O(E),所以Edmonds-Karp的时间复杂度就是O(V*E^2)。 如果能让每次寻找增广路时的时间复杂度降下来,那么就能提高算法效率了,使用距离标号的最短增广路算法就是这样的。所谓距离标号,就是某个点到汇点的最少的弧的数量(另外一种距离标号是从源点到该点的最少的弧的数量,本质上没什么区别)。设点i的标号为D[i],那么如果将满足D[i]=D[j]+1的弧(i,j)叫做允许弧,且增广时只走允许弧,那么就可以达到“怎么走都是最短路”的效果。每个点的初始标号可以在一开始用一次从汇点沿所有反向边的BFS求出,问题就是如何在增广过程中维护这个距离标号。 维护距离标号的方法是这样的:当找增广路过程中发现某点出发没有允许弧时,将这个点的距离标号设为由它出发的所有弧的终点的距离标号的最小值加一。这种维护距离标号的方法的正确性我就不证了。 由于距离标号的存在,由于“怎么走都是最短路”,所以就可以采用DFS找增广路,用一个栈保存当前路径的弧即可。当某个点的距离标号被改变时,栈中指向它的那条弧肯定已经不是允许弧了,所以就让它出栈,并继续用栈顶的弧的端点增广。为了使每次找增广路的时间变成均摊O(V),还有一个重要的优化是对于每个点保存“当前弧”:初始时当前弧是邻接表的第一条弧;在邻接表中查找时从当前弧开始查找,找到了一条允许弧,就把这条弧设为当前弧;改变距离标号时,把当前弧重新设为邻接表的第一条弧,还有一种在常数上有所优化的写法是改变距离标号时把当前弧设为那条提供了最小标号的弧。当前弧的写法之所以正确就在于任何时候我们都能保证在邻接表中当前弧的前面肯定不存在允许弧。 还有一个常数优化是在每次找到路径并增广完毕之后不要将路径中所有的顶点退栈,而是只将瓶颈边以及之后的边退栈,这是借鉴了Dinic算法的思想。注意任何时候待增广的“当前点”都应该是栈顶的点的终点。这的确只是一个常数优化,由于当前边结构的存在,我们肯定可以在O(n)的时间内复原路径中瓶颈边之前的所有边。 我程序做了很多优化(甚至包括动态内存分配的时候使用placement new进行优化),最终能做到比wxs写的dinic快了大约一倍,但程序只有一百二十多行,我对这个结果很满意。距离标号增广的确是一个非常优秀非常实用的算法。 示例程序(USACO Training Ditch): ditch.cpp

算法资料网站列表(收集中)

本列表收集算法资料丰富的网站,目前仅收英文网站。排名不分先后。 http://www.nist.gov/dads/ Dictionary of Algorithms and Data Structures,基本上各种数据结构和算法都会有介绍,个别的介绍太简短,没提供什么有用信息,大多数词条还是蛮有价值的,特别是有些More Information里面的链接。 http://oeis.org/ 在线数列百科全书。我只能说……谁用谁知道。 http://compgeom.cs.uiuc.edu/~jeffe/ Jeff Erickson教授的个人主页。这个教授真是一个好人,把自己的课程的一切资料——讲义、试题——放了上去。比如说那份详实的Algorithms Course Materials就是一份不可多得的好资料。 http://www.csse.monash.edu.au/~lloyd/ Lloyd Alison教授的个人主页。我发现里面关于某些东西(例如Suffix Tree)的介绍很不错,还有Algorithms->2D->Life里面的东西你一定要看看。 http://www.introductiontoalgorithms.com/ 一个关于Introduction to Algorithms这本书的网站,上面有用的资料不比原书中多。不过若你没有这本书,只是想对于某个算法找到其定义或者伪代码,这个网站还是有用的。 http://www.cs.fiu.edu/~weiss/ Mark Allen Weiss教授——Data Structures and Algorithm Analysis in C/C++/Java 等书的作者——的个人主页。这里有这些书的源代码,我认为这些代码是很好的。 http://www.cs.kent.edu/~rmuhamma/ Rashid Bin Muhammad教授的主页,里面的Algorithms页面挺有料。 http://courses.csail.mit.edu/ 一份MIT的课程列表,其中的6.851很神奇。 http://www.math.ucla.edu/~tom/ Thomas S. Ferguson教授的个人主页,我在上面下载了一份不错的Game Theory讲义。 哦……这个列表目前很短,因为我很菜,知道的东西还很少。如果你知道包含好的算法资料的网站,请一定要留言告诉我哦!

利用 Sparse Table 构造 Suffix Array

特别注明:这个算法是我昨晚神经抽筋想出来的,目前其正确性与时间复杂度没有经过任何验证。经过一定验证了已经,见最后。 设原字符串为S,长度为N。定义二维数组st[0..N-1][0..F](st代表Sparse Table),其中F为N在二进制下的位数(F=[logN]+1)。st中任一元素的取值为[1,N]中的整数,且满足st[i][f]与st[j][f]的大小关系(小于、相等、大于)与S的子串S[i..i+2^f-1]和S[j..j+2^f-1]的大小关系一致。上述“子串”中的元素可能越界,故在算法中认为任何下标大于等于N的字符均为一个比任意字符都要小的字符(如’/0’)。在已知st[k][f-1](0<=k<N)的所有值之后,子串S[i..i+2^f-1]与所有长度相同的子串的相对大小完全取决于st[i][f-1]⊕st[i+2^(f-1)][f-1](⊕为连接运算),若i+2^(f-1)>=N,可简单地认为上述连接运算的右值为0,所以所有长度为2^f的子串可以利用基数排序的方法在O(n)的时间内排序,这个O(n)的排序基于的事实是:给定元素的两部分的取值均为[0,n])。所以说可以利用O(n)时间求出st[k][f]。初始时st[k][0]的取值可以利用一遍计数排序求出,更简单地,可以令st[k][0]=S[k](当S的长度小于字母表的大小时,这有可能违反st中元素取值为[1,N]的定义,但由于把字母表的大小看作常数,这样处理不会影响复杂度分析)。在求出st[k][F](0<=k<N)的所有值之后,可以看出st[k][F]体现了S[k..N-1]在所有后缀中的(相对)位置,再经过一遍基数排序,就得出了后缀数组。O(nlogn)的时间复杂度是显而易见的。空间复杂度也为O(nlogn),可以利用滚动数组优化成O(n)。另外,利用上述st表可以用O(1)时间回答S中任意两个子串的大小关系。 update: 使用USACO DEC06 GOLD 的 Patterns 一题测试,可以AC,这个算法的正确性应该没问题,效率嘛……反正比那个用hash做的标程要快许多。一共写了85行,其中求Suffix Array的核心部分大约40行。 示例程序:patterns.cpp

过度热情计算

在Mark Allen Weiss的《数据结构与算法分析:C语言描述》中有这样一道习题(3.22a)。大意是扩展Stack这种数据结构,让它除了支持通常意义下的Push和Pop以外还要支持一个GetMin操作(取当前栈中的最小元素,并非DeleteMin),要求每个操作都要O(1)。 这道题我的解法是这样的:另外用一个栈,每当Push时在这里保存当前关于GetMin的答案。仔细品味一下这个方法,这就是over-eager evaluation(过度热情计算)!也就是说,我们在并不需要结果的时候就把结果计算出来。 对于某种数据结构,它要不断地被询问某个问题以及被修改,如果我们每次在被问及这个问题时才去计算它的答案,性能可能会不允许。但如果我们把问题的当前答案保存起来,在每次数据被修改时更新它(很可能要利用以前的答案来推得),并在被询问时直接返回保存好的答案,这可能会大大提高效率。很好的例子是一个会被经常问及所有元素平均值的集合。 与它相对的是lazy evaluation,懒惰计算,它的核心是尽量推迟真正进行计算的时间(甚至推迟到返回了“值”之后),直至不得不做。

平衡二叉查找树

二叉查找树是一种非常有用的数据结构。经过一定扩充,它可以支持的操作有:Insert(插入)、Find(查找)、Remove(删除)、GetMax(取最大)、GetMin(取最小)、Prev(取前驱)、Next(取后继)、Rank(取某元素的序号)、Select(按照序号取该元素)。如果数据是随机的话,以上操作可以保证在O(logn)的期望时间内完成。但是比赛中显然出题者会给出一些刁钻的数据让最普通的二叉查找树严重TLE,这便是平衡二叉树得以应用的时候了。平衡二叉树可以保证以上操作是严格(AVL)或均摊(Splay)或期望(Treap)的O(logn)的时间复杂度。 平衡二叉树的实现一般有三种情形:递归、Top-Down(自顶向下)、Buttom-Up(自底向上)。递归实现可能比较好写,比如Treap的递归实现就非常短,基本的插入删除二三十行就可以搞定。Splay的一种实现方法也是递归,但这种方法是不推荐使用的。因为Splay虽然保证均摊的时间复杂度,但并不保证高度(AVL保证高度是严格的O(logn)、Treap保证高度是期望O(logn)),这就造成面对某些刁钻的数据时虽时间上不会出问题,却可能由于递归层次过多造成栈溢出。(例如连续大量升序的插入会使Splay变成一条长链,此时访问最底端的节点就会造成栈溢出。)所以Splay比较好的编写方法还是Top-Down或者Buttom-Up,它们都是非递归的。其中Top-Down的核心Splay过程有大约三四十行,性能十分优异,虽然不太好理解但是强记住也是可取的。Buttom-Up的Splay我没写过,但我知道一切Buttom-Up的平衡树都需要维护每个节点的父指针,造成了一定的编程复杂度也容易出错(比如说最基本的旋转操作就比以前麻烦多了)。Treap也可以写成Buttom-Up,不过我觉得没必要——既然选择了Treap当然就是为了它的编程复杂度低,写Buttom-Up的Treap还不如写成Top-Down或Buttom-Up的Splay,没准行数还更少呢。但相对于递归实现以及Buttom-Up来说,Top-Down的缺点是很难维护每个节点的Size域(即这棵子树的节点数或者其左子树的节点数),事实上我一直认为Top-Down Splay是无法在均摊O(logn)的和不记录父指针的前提下加入维护size域的操作的——这两个前提若不满足则或失去了Splay的本质,或失去了Top-Down的精髓。综上所述呢,在考试时选择写哪种平衡树应该这样考虑:不需要Size且数据量极大时用Top-Down Splay,需要Size或数据量一般时用递归Treap,这两者我都有把握在15min内写对;Buttom-Up的唯一好处是既非递归又能维护Size,但似乎书写是最麻烦的,何况我没写过,所以就不考虑了。 下面说说平衡树的操作。Insert和Remove这种需要改变树中元素的操作因平衡方式而异,就不细说了。Find的基本方法就是不断比较待查找值与当前节点,若小于则向左,大于则向右,等于就找到了;Splay的Find有所不同,只要Splay这个值一下看看根部有没有就行了。 GetMax是从根一直向右走直至无法再走就找到了最大值,GetMin反之,注意Splay中还需要把找到的最值再Splay一下,否则无法保证均摊的复杂度。Prev是对当前值向左走一步然后一直向右,Next相反;对于Splay只要把它先伸展到根部再这样找就行了,但对于Treap,若它的左子树或右子树是空的,注意需要返回的反而是某个祖先节点,用递归实现或Buttom-Up比较简便。Rank操作只须记录每个节点的子树的大小,然后比较当前值与左子树的大小把它分到左边或者右边,如果分到右边要把左子树和当前节点的大小都加到答案里,一般就都采用非递归的实现了(反正是一个容易消除的尾递归)。Select基本与Rank类似,也是不断比较这个序号与左子树的大小,就能知道答案在左边还是右边了。 以上操作中GetMin、GetMax可以以每次操作相同的时间复杂度上界代替二叉堆,比单纯的二叉堆的优点是支持了方便的查找和删除,还可以同时找最大值和最小值。Prev、Next、Rank、Select等操作在很多题中也各有应用。 总的来说,对于这种用处广泛考察很多的数据结构来说,最好还是透彻地理解、熟练的背诵。