together: Find's Blog

今天, 我无耻地做了一名逃兵. 结论是我的人权主义思想是完全不适应这个社会的. 我打算慢慢地学会以一个野人的角度看待问题, 免得与我们的社会产生更大的冲突, 使得自己痛不欲生接而再令别人痛不欲生. 具体内容, 当军训结束后, 会另写一篇文章.

在逃亡日, 我总结了这些天来( 一个月了吧 )对网络流的感触. 由于战略安排, 我的网络流学习效率十分低下. 但不管怎么说, 我学到了很多. 教材是CLRS.

流, 形象地说, 就是水流在一个水管网络中行进的量与路径. 最大流, 就是能够将水流尽可能多地从s运往t的一种流, 即流的值最大. 流有容量限制, 反对称性, 流守恒性这三个性质. 容量限制, 就是通过水管的水流不能把水管给撑爆了, 它得低于水管的流量限制. 反对称性, 即水管从左向右运过来x单位的水, 我认为有更好的运送方案, 所以我可以将不超过x的水再沿这个水管从右到左给它送回去. 流守恒性, 水流在通过这个网络时, 不可以消失, 不可以增加. 即只有自来水公司可以供水, 只有下水道可以消耗水( “永远”地占有水 ), 而各位用户和传输用的管道没有产生水的能力, 也没有将水据为己有的权力,他( 它 )们必须把这些水流原封不动地传给他们的邻居.

最大流等于最小割, 这事太麻烦, 不细说了. 所谓最小割是一个边的集合, 去掉这些边从s到t将不再存在路径, 同时这些边的容量限制之和最小. Amber牛在他2007年的集训队论文中详细地证明了这个定理, 大家跑 http://adn.cn/blog/article.asp?id=55 找找看.

残留网络是在当前流f经过之后, 图中所有仍能传输流的边所构成的. 增广路径是残留网络中从s到t的一条路径.

Ford-Fulkerson是解决最大流的一个很直接的办法. 就是不断地找增广路径. 当增广路径找不到了时, 当前流显然是最大流. 其复杂度O( mf ), 其中f是最大流的值.

Edmonds-Karp算法是对Ford-Fulkerson算法的一种改进, 它按边数的递增顺序选择增广路径的. 其复杂度是 O( nm^2 ).

Dinic算法是对Edmonds-Karp算法的一种改进, 它是进行一次BFS, 多次DFS, 即一次做距离标号分层, 然后多次用O( m )的时间复杂度找路径. 其复杂度是 O( n^2m ).

当我们考虑完这三个家伙的祖孙关系之后, 我们用另一种方法解决最大流问题, 预流推进.

预流推进时用到前置流的思想, 所谓前置流, 是假设一下涌出去尽可能多的流, 而每个中途顶点有一个”水库”, 可以暂时的存贮这些流的一种流, 也就是一种放宽了流守恒条件的流. 一个比较优秀的实现的时间复杂度是O( n^3 ). 它对各顶点的考虑顺序是按一种容许边( 即残留网络中的边 )的拓扑排序来的, 至于为什么容许边可以被拓扑排序, 这需要用预流推进的高度函数来证明残留网络是有向无环图, 这里就不细说了.

预流推进还有一种实现方法说是可以以O( n^2 * m^0.5 )的时间内完成, 但是由于找不到时间复杂度的证明, 再加上看到关于流的描述已经开始有了想吐的冲动, 这个算法没有仔细研究.

比较目前已知的找增广路径和预流推进的算法, 我们可以看到, 尽管似乎预流推进的时间复杂度较低, 找增广路的方法时间上限较高, 但是在一个随机的图中, 很难达到这样高的一个界, 增广路径一般很快就会被找完, 因此这种方法的性价比是很高的. 而预流推进的上限却比较紧. 再加上OIBH上投票的情况, 在数据规模不大的情况下, Dinic是王道.

现在遗留的问题是那个最高标号预流推进. 这个问题, 过上一个月再想. 九月份开始解决一些杂碎的算法问题, 包括矩阵算法, 数论算法等等, 然后把USACO解决掉.