第12章 有向图就是边是顶点的有序对的图，也就是说每个边都有起始顶点和终止顶点。任意两顶点间有且仅有一条边的有向图叫竞赛图。若任两顶点间都可以沿有向路径互达，图就是强连通的。 无向图的强连通定向就是把每条边指定一个方向，然后保证得到的有向图是强连通的。强连通定向存在当且仅当原图中没有桥。构造出这一强连通定向事实上很简单：按照一遍DFS的访问方向给边定向就可以了（书中的算法一如既往地麻烦）。 核心分配问题是这样的：n个商人，每人有1个商品，每人对所有n个商品按照自己的喜好进行排序。求一个把n个商品分配给n个人的方案，使不存在几个商人的集合，他们把分到的商品再次进行交换后可以使每个人都更满意。算法是：每个商人对自己最喜欢的商品的主人连一个有向边，找一个圈（由于每个点都有出边，所以这肯定是能找到的），按照这个圈进行分配，把已分配的顶点删掉，所有指向这些顶点的边重新计算。 网络就是存在源点s和汇点t的有向图，其中每条边都有一个可以认为是“容量”的权值。网络中的流定义为加在每条边上的一个函数，也就是说给每条边指定一个“流量”。合法的流应该满足：每条边的流量不超过其容量，除源点和汇点外，点的出边的容量和与其入边的流量和相等。流的净流量就是源的出边的流量和或汇的入边的流量和。求一个合法的净流量最大的流就是最大流问题。 网络的割是一组边的集合，满足把这些边从原图中删去后从源点到汇点不再连通。最小割就是边的权值（就是上述“容量”）和最小的割。最大流最小割定理的内容就是：网络中的最大流的值等于最小割的值。 求解最大流问题和最小割问题可以采用残量网络增广路的方法。这在很多很多资料中都有很好的介绍。《组合数学》这书似乎并不是学网络流的好教材。 第13章 χ(G)是图G的色数，就是说给图的每个顶点赋一个颜色使所有边的两个端点的颜色不同，需要的最少颜色数目。它也可以理解成将顶点划分成若干个集合，使每个集合的导出子图都是零图的最少集合数目。求图的色数很困难。 关于图G的色多项式pG(k)，也就是说将图G用k种颜色的方法数。有一个结论：设T是一棵n阶树，则pT(k)=k(k-1)^(n-1)。它的证明也简单：第一个顶点有k种着色方式，以后每添加一个与当前顶点相邻的顶点都k-1种着色方式（因为它仅与一个顶点相邻），根据乘法原理得证。另外，n个顶点的零图的色多项式是k^n。求色多项式的一种方法是：当G不为零图时，设x、y是一对邻接顶点，设G1为原图去掉边x、y的图，G2为原图将x、y合并成一个顶点的图（原来与x或y相邻的顶点均与新顶点相邻），那么就有pG(k) = pG1(k) – pG2(k)，递归求解即可。这个算法的正确性还比较好理解的，不过显然它是指数级的算法。它可以采用非递归的方法实现，就是维护一个图的集合，每次取出一个非零图的元素把它分成两个元素。 平面图就是可以“画”在平面上而且边不交叉的图。（更“数学”的定义似乎书上没有。）它有一些很好的性质：设一个连通的平面图的平面表示有n个顶点点、e条边曲线、r个所围区域，则：n+r-e=2。证明的方法是先对树证明，再往树上加边，保持等式始终成立。一个平面图必存在一个顶点，它的度至多是5，这是欧拉公式的推论。 五色定理是：一个平面图的色数至多是5。这个可以比较简单地证明，主要根据上面的欧拉公式的推论来利用那个特殊的顶点做突破口。它的加强版本四色定理也是成立的。 图的独立集的定义是一个顶点的集合，它的导出子图是零图。图的独立数α(G)就是图中最大的独立集的大小。求图的独立数很难。图的控制集是一个顶点的集合，它满足所有不在集合中的顶点都与集合中的点有边。最小的控制集的大小称为图的独立数dom(G)。图的团就是一个顶点的集合，它的导出子图是完全图。图中的一个团是图的补图的独立集，反之亦然。图的团数ω (G)是最大的团的大小。将图的点集划分成最少的团的数目称为团划分数θ(G)。完美图满足它的任何一个导出子图有χ(G)=ω (G)且α(G)=θ(G)。 图的弦就是连接圈的两个顶点且不属于该圈的一条边。如果每一个长度大于3的圈都有弦，图就被称为弦图。所有的弦图都是完美的。所有的区间图（定义不说了）都是弦图。 以上定理的证明均略，因为第一我也搞不太懂，第二它们在OI中似乎没什么用。 图的顶点连通度κ(G)是最少删去多少个顶点可以使图不再连通，定义κ(K_n)=n-1。边连通度λ(G)是最少删去多少条边可以使图不再连通。再设δ(G)表示图中顶点的最大度，则有显然的不等式κ(G)≤λ(G)≤δ(G)。 顶点连通度κ(G)不小于k的图称为k-连通图，一个图是2-连通图与以下结论等价：没有关节点；任两个顶点a、b都存在一个包含a、b的圈；每三个顶点a、b、c，都存在一条连通a、b且不经过c的路径。这些都很好证明。 关于图的点连通度的Menger定理的内容是这样的：设k是一个正整数，G是一个阶为n≥k+1的图，则G是k-连通的当且仅当对任意两个不同的顶点a和b都存在连接a、b的k条路径使得每对路径只有a和b两个公共点。
昨天的梦里，我有了一个“女朋友”。醒来后，几乎一切情节都忘记了，记得梦中那女孩的脸红红的，很可爱的样子。还记得梦里洋溢满心的幸福与平和。 梦里肯定有我与那女孩的相识相知相恋的全过程，这一点我可以确定。但是醒来以后却全部都忘记了。唯一清晰留在脑海中的一个情节片断是这样的： 我：“我以后全都听你的好吗？” 她：“那怎么行呢。” 试图借助Frued的理论分析这个片断，却得到很不好的结果…… （不，我的精神分析没有你想得那么表面。）
第14章 直线型代码有两种，一种是语句之间有（可能是极隐蔽的）前后依赖关系，另一种是顺序无关的语句。 对于依赖关系的语句，应该设法让这种依赖关系表现得极为明显，比如说第二个函数调用的参数是第一个函数调用的返回值，或者说它们有共同的（按引用传递的）参数。当然，也可以用数据来表明没有依赖关系的语句。 至于顺序无关的语句，也应该尽量让相关（操作于同一对象）的语句放在一起。也就是说，应该让越靠近的语句关系越大。 第15章 if语句的一种常见用途就是区分正常情况与异常情况。应该把正常情况放到if前面然后异常情况用else处理，这是一种好的习惯。但我认为如果所有的代码逻辑都是异常情况用if，似乎也不会带来太大困扰。特别是在遇到异常情况就会return的情况，先处理了所有异常情况，然后在“净室”的环境下写正常情况的代码，减少了缩进层次，似乎也会更清晰。这是我的编程习惯。 if-then-else语句串的排列一般采用常见的情况在前的方式来处理，这样可以（很不明显的）提高效率。case语句是类似的。提倡尽量在每一case语句后都break，否则很容易令人困惑。 第16章 循环有好多种，不过在OI中选择哪一种似乎是自明的。应该尽量避免在循环体内外重复语句，虽然有时候看上去是不可避免的。 循环的控制语句和循环的内部最好应该可以互相看作黑盒，完全分离。 循环的初始化代码应该紧紧放在循环前面。当这种代码进有一句时，把它放到for的第一个语句似乎是更好的选择。 尽管C中的for很强大，但是一般应该让循环头中的语句仅与循环控制相关。其实还是循环的控制和循环的内容分离。 使用continue可以避免一个能让整个循环体都缩进的if判断。 减少off-by-one错误的好方法是在脑海或者用纸笔模拟，对于优秀的程序员来说这不应该太费时。 我觉得在OI中采取从内而外编写循环的方法学不是个好主意。 第17章 如果能增强可读性，那么就使用return。 对于goto，我的观点是：永远不要用。事实上我坐到了这一点。 第18章 表驱动法是一个好主意，应该了解。其实OIers对于这种东西应该比一般的“程序员”熟些，大部分情况下，不就是一预处理么，呵呵。
1，《组合数学》《Code Complete》两书看完并写完全部的缩写/笔记，这个尽量快些，每天都要有进度。 2，后缀数组要会O(n)算法，height相关的东西要写熟；后缀树的话，至少会个O(nlogn)吧，要多做几道相关的题。串处理方面一定要加强，看论文，看CLRS。 3，做SGU，所有1000+的题目要都做掉，然后写一个阶段的总结。然后开始做600+的，尽量也都做掉。看看有没有相关的好玩儿的数据结构/算法（估计不太有）。 4，本月暂时不学Vim和Linux。 5，不能荒废时间，放松一下可以，你知道怎么样算荒废时间。
第9章 这一章讲二分图中的匹配。给出了几个能启发思路的转化成二分匹配的模型：有禁止的棋盘上放非攻击车；有禁止的棋盘上放1×2骨牌；m个具有一定资格的人申请n个工作。将问题转化为二分图匹配模型的关键点是构造二分图，使可行解与合法的匹配一一对应，这样最优解一般就对应了最大匹配。 定义二分图的交错路径是这样一种路径：含有奇数条边，其中仅有第1条、第3条、……、最后一条边都没有包含在当前的匹配方案里，仅有路径的两个端点没有被匹配。一个匹配是最大匹配当且仅当不存在交错路径。求最大匹配的方法就是不断寻找交错路径并将使用其中的奇数边重建当前匹配方案的，这就是Hungary算法。书中给出的伪代码垃圾了，本来不用那么麻烦的，更好的代码参见我以前关于Hungary算法的文章 二分图的最小覆盖的意思是这样的：选定一些点，让所有的边都有端点被选择，选的点数尽量少。König定理是这样的：二分图的最大匹配数等于最小覆盖数。这个定理可以帮助解决另一类可以转化为二分图匹配模型（先转化为最小覆盖模型）的问题。 一个和二分匹配有关的问题叫稳定婚姻系统。似乎在OI中用途不太大（主要是不太具扩展性），问题和算法（延迟认可算法）我不描述了。 （第10章暂略） 第11章 图就是由顶点和边构成的东西，（无向或有向的）边可以认为是顶点中的一种（可交换或不可交换的）关系。顶点的度就是邻接的边的数量，如果是有向图的话还可以定义入度和出度。 欧拉路就是一条经过了所有边仅一次的（不一定是简单）路径。存在欧拉路的充要条件是有0个或2个度为奇数的顶点，前者的欧拉路的起点与终点是闭合的。欧拉路可以用圈套圈算法来求。不过书中的方法实现起来还是麻烦（需要写链表），有更好的方法。中国邮递员问题，就是求一条从一个点出发经过每一条边再回到起点的最短路径。解决这问题的大概想法就是通过添边把所有奇度顶点变偶。问题的算法书上没写，不过我想大约就是：找出所有奇度顶点求它们两两的最短路，然后求（非二分图的……）最优匹配。如果是有向的反而简单的多，因为这样可以根据负点和正点构造出二分图匹配。 Hamilton路径的定义就是一条经过所有顶点仅一次的路径。这是NP-Complete问题，目前没有多项式算法。 判断图是否是二分图只需要试图给图2涂色，如果涂出矛盾了就不是。 树是一种图，它的定义包括：任两点都有且仅有一条路径的图；不含圈的图；n个顶点n-1条边的连通图。 Shannon开关游戏很有意思。正方必胜策略的有无取决于图是否存在两个不存在重复边的生成树，如果找出了这两个生成树，必胜策略的算法还是不太复杂的。不过这两个生成树怎么找呢？ 求最短距离树，其实就是求单源最短路径，所有的最短路径（可以）是一棵源点为根的树，用Dijkstra算法求。最小权生成数用Kruskal算法或Prim算法求。