poj 2949 Word Rings (spfa+栈优化)

2016年5月25日 0 作者 CrazyKK

poj2949 题目链接
题意:我们有 n 个 (n<=100000) 字符串,每个字符串都是由 a~z 的小写英文字
母组成的字符串。如果字符串 A 的结尾两个字符刚好与字符串 B 的开头两字符相
匹配,那么我们称 A 与 B 能相连(注意: A 能与 B 相连不代表 B 能与 A 相连)。
我们希望从给定的字符串中找出一些,使得他们首尾相接形成一个环串(一个串首尾相连也算)
我们想要使这个环串的平均长度最长。

思路:参考了国家集训队论文《spfa算法的优化与应用》

首先我卡在了关于接龙问题的处理方法,只能想到n^2的方法。。显然gg.

而正解是把每个单词看做一条边,把每个单词开头的两个字母和结尾两个字母看做起点和终点,由于都是小写字母,2位26进制数最多表示26*26。

这个建图方式并不是特别显然,不过想一下还是可以理解的。。以及这应该算是处理单词接龙问题的一个技巧。。。

 

这道题综合了两种常见的问题:字符串的接龙以及平均值的最优化问题。对于前者,我们可以采取把单词看成边,把首尾字母组合看成点的方法。例如对于单词ababc就是点”ab”向点”bc”连一条长度为5的边。这样问题的模型变得更加清晰,规模也得到减小。那么原问题就可以转化成在此图中找一个环,使得环上边权的平均值最大。对于这种问题,我们有很经典的解决方法:

由于Average=(E1+E2+…..+Ek)/K
所以Average*K=E1+E2+……+Ek
即(E1-Average)+(E2-Average)+….+ (Ek-Average)=0
另外注意到上式中的等于号可以改写为小于等于,那么我们可以二分答案Ans,然后判断是否存在一组解满足(E1+E2+…..+Ek)/K>Ans,即判断
(E1- Ans)+(E2- Ans)+….+ (Ek- Ans)>0
于是在二分答案后,我们把边的权值更新,问题就变成了查找图中是否存在一个正环。

 

然后参考了这篇题解学习了一下栈优化的spfa: spfa栈优化   

以及这篇博客中比较了dfs的spfa和普通栈优化的spfa… 200+ms vs 2000+ms…十倍的优化。。太神了。。。

 

/*
枚举每一个平均长度mid值。
如果存在一个环,(E1+…+Ek)/k>=mid(其中k是边数,E1……Ek是各个边权),
那么正解比mid大,否则比mid小,这就是二分策略。
那么怎样知道是否存在(E1+…+Ek)/k>=mid 呢?
如下转化:(E1+…+Ek)>=mid*k
E1-mid + E2–mid + E3-mid + … + Ek-mid >= 0
所以,把所有的边权改为Ei – mid,然后看是否存在正环就可以,存在就是满足条件。
*/