1、前言
今天说实话并不算太难的吧，没太多好说的。
2、Transform 变换序列
来源：BZOJ 1562 / NOI2009
链接：http://www.cnblogs.com/jinkun113/p/4893387.html
3、Graph 最大子图
来源：BZOJ 1093 / ZJOI2007
链接：http://www.cnblogs.com/jinkun113/p/4894712.html
4、Dist 最短路
大概题意：给定平面上的n 个点，定义(x1,y1)到(x2,y2)的费用为min(|x1-x2|,|y1-y2|)，求从1 号点走到n 号点的最小费用。
总结：考试的是想方设法找到能够简便的方式进行判断，觉得应该是要从一些点去寻找突破口的，但是很久都没有发现，只能直接暴力连边去跑SPFA了。
题解：
最短路是显然的，但是同样暴力连边会TLE也是显然的。这个时候我们要想个办法找到一些没有用的点删掉。假设当前存在两个点i，j，x距离为|xi-xj|。若存在一个点k，有xi<=xk<=xj，则从i到k然后从k到j，必定不会比从i到j差。为什么？因为还要考虑y方向的距离，如果|yi-yk|+|yk-yj|<=|xi-xk|+|xk-xj|，显然是要优于或等于从i到j的；如果|yi-yk|+|yk-yj|>|xi-xk|+|xk-xj|，那么和从i到j答案相同。
所以在连边的时候，首先将所有点按x排序，相邻点相连；再按y排序，相邻点相连。接着跑O(n log n)的Dijkstra吧（别用SPFA作死）。
5、Planar 平面图判定
来源：BZOJ 1997 / HNOI2010