2015/06/18

图论专题总结

P.S. 这篇主要是自己记记玩玩的,可能只有我一个人看的懂…

图论就这么浩浩荡荡搞了一个多星期…感觉很一般。
随着专题并没有什么思路,这几天跟着大白皮过了一遍,那就随着这个思路再过一遍知识点,复习一遍经典题。



图的一些基础概念无需多说。而图的应用中,最直接的就是搜索。这里重点提及一下隐式图搜索,说白了,就是把题中给定的情况,分离出多种状态,在各个状态中连上边权适合的边,以将其转化成一个图论问题。这种方法的应用非常广泛,一些特性也很值得挖掘。
[UVa 10047 The Motocycle] 朝向和底层颜色构成状态。
[LA 4255 Guess] 转化为前缀和,做拓扑。
其实这几次考试中也出现了几次隐式图搜索,但当时并不知道= =

深度优先遍历。深度优先遍历本身是种暴力,也可以计算连通分量等,然而搭配上时间戳DFN和LOW,就变得很神奇了。分别来说:
无向图。无向图的割顶LOW值≥DFN,据此线性时间可找出所有割顶,同时,若割顶的儿子只能连回自己,那割顶与儿子之间的路则为桥;双连通分量,点-双连通分量即常说的双连通分量,指任意两点存在点不相同的路径,边-双连通分量指意两点存在边不相同的路径,可以看出,两个点-双连通分量之间至多有一个公共点;如何求。点-双连通分量:类似于Tarjan,但是把边加入栈,当后代的Low值≥DFN时退栈直到当前边,则退出栈的这些边连接的点属于一个点-双连通分量,边-双连通分量:更简单,删掉所有桥,剩下的连通块分别属于同一个边-双连通分量。
[LA 5135 井下矿工] 对于连通分量性质的考察比较全面。
有向图。强连通分量(SCC),可用Kosaraju或Tarjan,不再赘述,常用于缩点。
[LA 4287 等价性证明] 得到一个有趣的性质:使一个DAG成为强连通分量的最小边数为min(入度为0点数,出度为0点数)。

图论的构造类也非常有意思,但做题少没办法说出些什么。另外,相关的一些知识,如仙人掌也有所涉猎,再复习下2-SAT:
2-SAT。问题的定义见书,简单来说,就是如果a发生将导致b的发生,就连接a–>b,运用黑白点标记来求解。
以上问题,虽然理论知识是懂了,但题目并是做的很少,以后有时间可以专门做一做,也可以不定时做一做巩固。

下面说讲课的这三个专题。

生成树。(直接复制的前几天的一篇Dairy)我从一个月前接到讲课的任务,不知怎么就选了最小生成树,自己开始搞后,其实发现有很多东西,我适当的加深了难度,然后自己也看了很多题,应该是学的可以。然而我自己懂了之后,发现又两个很严重的问题:我并是没有打过一道题目,而且我并没有想好怎么讲课。其实后面打一本通的时候发现很好打,于是就决定跟进度同步,一起打了。然后就是讲课的问题,自认为ppt上的思路很清晰了,然后主要就做了做特效,做了很久了,之后也没去管它。到今天讲课的时候我发现忘掉好多东西了…应该再看一看的,尤其是开始两道例题,第一问我题目都忘得差不多了,第二问我是也没有太明白,当时也没太管,不过知道它的思路,我就这么强行口糊下去了,之后也口糊了不少地方…总之算比较失败把这次…然而其实我自认为表达能力是比较强的…然后经常就是某个人问题目问别人听不明白问我就明白了…然而这次主要的问题大概就是实在那几天没怎么准备吧…
对于最小生成树的问题,其实很多都是从性质出发衍生出的问题,若是能深度挖掘最小生成树的一些特殊性质,题目应该很好做。
[BZOJ 1601 灌水] 有种很机智的做法,锻炼思维。

最短路。非常明确简单的思路,应用和变化也很多。四个算法都用得到,问题类型有多源最短路,单源最短路,K短路,传递闭包,查分约束,有时配上简单枚举,常用于隐式图搜索。
掌握的都差不多(除K短路),主要还是缺乏练习,以后要通过大量题目来巩固。
[UVa 11374 机场快线] 简单题竟然自己没想出来,立起来提个醒。
[LA 4080 战争和物流] 挖掘最短路树性质。
[POJ Intervals] 查分约束经典题。
[UVa 11478] 更机智的查分约束。
[UVa 11090] 模型和上题差不多但做的事并不相同。

拓扑排序。还是比较扎实,很多题1A。但对更深层次的应用不熟,比如判负环,可以判断DAG上任意两点是否单向可达,虽然一说就懂,但是还是想不到sad…像什么反向拓扑序,完全不符合正常人的思维啊…
[HNOI 2015 Dishes] 经典题
[HDU 3424 Triangle LOVE] 有趣的性质
[POJ 2762 Going from u to v … to u?]判断DAG上任意两点是否单向可达
图论的这些题与DAG,DP也都结合紧密。

另外的。
原准备涉猎一点二分图和网络流,然而急急忙忙开始数学,也只好先标个签以后再说。
二分图和匹配其实看完一半了,判断就是是否有奇圈(定义),或黑白染色。
其他也没什么好讲的了,主要还是做题,巩固。

–By Foggy
2015.6.17 深夜