1、网络流PKU 1149 不错的题目，算法我在之前的帖子里已经讲了 SGU 176 容量有上下界的网络流问题，有难度 UVA 563 点不交的路径条数问题，需要拆点 ZJU 1553 判定一个最大流是否最小费用，用klein圈迭加算法（其实就是找负权回 路） 2、计算几何 ZJU: 1032 需要了解一个公式1081 经典，判点是否在多边形内，推荐1128 矩形并的面积（其实不算是计算几何）1158 比较麻烦的计算几何+图论1193 不错的也很基础的计算几何，推荐1199 基础，不过好像精度容易出问题1280 基础1296 强烈推荐，向量旋转1377 类似凸包，推荐1453 凸包1296 强烈推荐，向量旋转1465 凸包，推荐1521 计算几何+动态规划，强烈推荐1562 可以扫描，也可以动态规划，强烈推荐UVA: 10256 很好的计算几何，强烈推荐SGU: 110 ZJU1193的加强版 120 主要是数学 129 基础，推荐 Ural: 1075 强烈推荐1093 3维的计算几何，推荐3、差分约束 差分约束系统是指形如AX<=B的一个不等式组，其中A的每行恰有一个1和一个-1， 其它元素都是0 这样的系统可以转化为图论的最短路模型，可以很巧妙的解决一些很难的题目 这个链接里有一些关于差分约束系统的介绍差分约束系统，就是求出满足简单线性不等式组xj-xi<=bk的解。 根据不等式，可以构造出约束图。可以证明，如果约束图中存在负权环，则无解， 否则从约束图新构造的v0出发的单源最短路径就是问题的一组可行解。 由于约束图中有负权，我们可以使用Bellman-Ford算法来解决最短路径问题。http://icl.pku.edu.cn/yujs/papers/pdf/ComAlg18.pdf 大家也可以去oibh.ioiforum.org里面下载郭一的论文看看，里面讲到的NOI99的那 题“01串”就是一个典型的差分约束系统 ZJU上有几道难题可以用差分约束系统解决，大家可以看看差分约束系统的理论之 后想这些题目 1260（这题相对简单一点） 1420（这题需要一定的转化，不那么好想） 1455（CTSC97的题目，典型的差分约束系统） 1508（CERC2002的题目，标程用贪心，但实现起来比较复杂，远不如用差分约束系统简单明了） PKU1201=zju1508 PKU17164、树型动态规划比如，给出一棵树，每个节点有一个权，求一棵子树，使得其顶点的权值最大 或者，给出一棵树，树边有一个权代表节点间的距离，对每个节点，求出它到其它 节点的最远距离这两个问题用树形dp来做的话都是O(N)的树形dp有一定的技巧性，也有一定的规律性一般来说，都是从叶子到根的顺序访问节点可惜ZJU没有相应题目，只好推荐ural和saratov的 ural 1018（这题的数据很有问题，建议不要做） 1039（很典型的树形dp） 1056（求树的中心） saratov 134（有点像求中心，不过麻烦一点点） 143（很典型） 5、动态规划 1011（其实...这也算是个树形dp） 1013（看起来远比做起来复杂，复杂度很高的程序也ac了） 1027（简单但典型，类似公共子串问题） 1074（经典） 1074（经典） 1102（其实也算树形dp，推荐） 1147（有点难） 1161（典型，推荐） 1183（和1161差不多） 1196 1206（不错的题） 1227（典型但有一定难度） 1234（很好的动态规划题目，强烈推荐，lrj出的题） 1387（看谁的程序快^_^） 1499（推荐） 1554（推荐） 6、二分图最大基数匹配 这也算是一个很基础的知识了，算法一般用匈牙利算法，而用网络流可以达到更快 的速度二分图匹配的题目在ZJU是很多的，这里推荐一些： 1059 1077 1137（需要转化） 1140（容易，直接匹配） 1197 1364（需转化，模型不明显） 1227（典型但有一定难度） 1525（这题要用到另外一个知识点...） 1568（wishingbone出的题^_^）
