t 是我最近在网上看到推荐的一个todo工具，它比较另类，不同于常规的todo app是基于web或client的，而是在Command-Line上的一个工具，这个todo工具让我眼睛一亮，就像当年看到 Octopress 一样。 以前用过Wunderlist，RTM，最近都一直用的是Any.do，挺简洁的一款todo app，Chrome上有插件，唯一一点不爽的就是基于网速的原因(也可能是其他原因)，有时点了图标，但是半天才出来todo list，或者有时就出不来，这样的感觉太难受了。而我的工作环境是VMware下Gentoo终端里，自然更倾向于一些可以本地保存的命令行工具，所以 t 非常符合我。
Edmond Karp算法的大概思想： 反复寻找源点s到汇点t之间的增广路径，若有，找出增广路径上每一段[容量-流量]的最小值delta，若无，则结束。 在寻找增广路径时，可以用BFS来找，并且更新残留网络的值(涉及到反向边)。 而找到delta后，则使最大流值加上delta，更新为当前的最大流值。 (粗体表明需要掌握的概念)
Huffman树，中文霍夫曼树或哈夫曼树，又称最优二叉树，是一种带权路径长最短的树。 Huffman树的构建思想： 1.从原始元素集合T中拿出两个频度最小的元素组成一个二叉树，二叉树的根为这两个节点频度的和。 2.然后从集合T中删除这两个元素，把根元素加入到T集合中，如此反复直集合T为空。 构建此过程的数据结构： 1.优先级队列 2.顺序存储结构 3.二叉链表（本文所用） 逐步分析： 1.Huffman树的结构(二叉链表表示): 1 2 3 4 5 6 typedef struct{ unsigned int weight; unsigned int parent, lchild, rchild; }HTNode, *HuffmanTree; //动态分配数组存储哈夫曼树 typedef char* HuffmanCode; //动态分配数组存储哈夫曼编码表 2.SelectMin函数用于筛选最小的两个数，其中s1用于保存最小的，置于左孩子结点，s2保存第二小的，置于右孩子结点： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 [...]
首先说一下，ACM的入门方法多种多样，大部分人还是跟着学校一起参加集训，所以我这里主要是想对那些准备ACM入门的业余的朋友谈的。 入门书籍： 首先推荐一些ACM的书籍： (以下我都会给出在当当网的页面，方便大家直接购买，以下排名不分先后) 1.《程序设计导引及在线实践》 http://product.dangdang.com/product.aspx?product_id=20051430&ref=search-1-pub 这是我的第一本入门书，这本书是配套北大的百炼习题，注意不是POJ，貌似是北大内部测试用的，不过也是对外开放的，去年好像百炼变化过，所以不知道这本书还适不适合那个新的百炼系统。 2.《算法竞赛入门经典》 http://product.dangdang.com/product.aspx?product_id=20724029&ref=search-1-pub 这本书没话说，刘汝佳的白书，经典的算法入门书籍。强烈推荐！ 3.《算法艺术与信息学竞赛》 http://product.dangdang.com/product.aspx?product_id=8811386&ref=search-1-pub 刘汝佳的黑书，难度较深，题目基本来至Uva，我是看了前面以部分，后面就没咋看了。。。 4.《算法导论》 http://product.dangdang.com/product.aspx?product_id=9211884&ref=search-1-pub 经典的书籍是不需要解释的。 这是我曾经上传过的英文版CHM算法导论，可以下载了看看： http://www.cppleyuan.com/viewthread.php?tid=5130&highlight=%E7%AE%97%E6%B3%95%E5%AF%BC%E8%AE%BA 我最近也在写算法导论的读书总结，欢迎大家探讨： http://www.wutianqi.com/?p=2403 5.《编程之美》 http://product.dangdang.com/product.aspx?product_id=20170952&ref=search-1-pub 挺有意思的，不能作为一个算法的全面书籍，而是作为一本拓宽思维的书籍，有兴趣的建议要看看。 6.《计算机程序设计艺术》 http://product.dangdang.com/product.aspx?product_id=690222&ref=search-1-pub 有好几卷的，只给出一卷的连接，而且网上版本很多，大家可以自行选择。 这个还没看，关键是没时间了，准备考研完了就趁着假期看完。 7.《组合数学》 http://product.dangdang.com/product.aspx?product_id=8976756&ref=search-0-mix 鸽巢原理，博弈，容斥原理，Catalan数等都属于这个范畴的，建议看看。 8.《数据结构（C语言版）》严蔚敏 http://product.dangdang.com/product.aspx?product_id=9268172&ref=search-1-pub 数据结构，这个必须得学好啊~~~ 9.《数据结构与算法分析C++描述（第三版）》 http://product.dangdang.com/product.aspx?product_id=9239535&ref=search-1-pub 有时间可以看看，C++ Template写的，可以顺便巩固下template。 以下基本都没看过，不过貌似很有名，给出书名和连接： 10.《世界大学生程序设计竞赛（ACM/ICPC）高级教程.第一册.程序设计中常用的计算思维方式》 http://product.dangdang.com/product.aspx?product_id=20645866&ref=search-1-pub 这本我其实买了，但是还没有时间看。 11.《国际大学生程序设计竞赛指南—ACM程序设计》 http://product.dangdang.com/product.aspx?product_id=20450827&ref=search-1-pub 12.《国际大学生程序设计竞赛例题解（三）图论、动态规划算法、综合题专集》 http://product.dangdang.com/product.aspx?product_id=9352432&ref=search-1-pub 这个好像也有好几册，每一册都是单独讲一个方面的。 13.《挑战编程：程序设计竞赛训练手册》 http://product.dangdang.com/product.aspx?product_id=20637355&ref=search-1-pub (作者：Tanky Woo, 个人博客：http://www.wutianqi.com ，C++/算法论坛：http://www.cppleyuan.com/ 。转载请注明个人及原文连接，谢谢合作) 入门方法： [...]
建议看SPFA前先看看Dijkstra和Bellman-Ford这两个最短路算法。 SPFA的思路比较简单，网上的说法也比较统一，NOCOW和百度百科上都有。这里在网上找到讲的比较通俗易懂的： SPFA(Shortest Path Faster Algorithm) 是Bellman-Ford算法的一种队列实现，减少了不必要的冗余计算。 算法大致流程是用一个队列来进行维护。 初始时将源加入队列。 每次从队列中取出一个元素， 并对所有与他相邻的点进行松弛，若某个相邻的点松弛成功，则将其入队。 直到队列为空时算法结束。 它可以在O(kE)的时间复杂度内求出源点到其他所有点的最短路径，可以处理负边。 SPFA 在形式上和BFS非常类似，不同的是BFS中一个点出了队列就不可能重新进入队列，但是SPFA中 一个点可能在出队列之后再次被放入队列，也就是一个点改进过其它的点之后，过了一段时间可能本 身被改进，于是再次用来改进其它的点，这样反复迭代下去。 判断有无负环：如果某个点进入队列的次数超过V次则存在负环（SPFA无法处理带负环的图）。 SPFA算法有两个优化算法 SLF 和 LLL： SLF：Small Label First 策略，设要加入的节点是j，队首元素为i，若dist(j)<dist(i)，则将j插入队首， 否则插入队尾。 LLL：Large Label Last 策略，设队首元素为i，队列中所有dist值的平均值为x，若dist(i)>x则将i插入 到队尾，查找下一元素，直到找到某一i使得dist(i)<=x，则将i出对进行松弛操作。 引用网上资料，SLF 可使速度提高 15 ~ 20%；SLF + LLL 可提高约 50%。 在实际的应用中SPFA的算法时间效率不是很稳定，为了避免最坏情况的出现，通常使用效率更加稳定的Dijkstra算法。 其他最短路算法： 最短路径算法—Dijkstra(迪杰斯特拉)算法分析与实现(C/C++) 最短路径算法—Bellman最短路径算法—Floyd(弗洛伊德)算法分析与实现(C/C++) 最短路径算法—Floyd(弗洛伊德)算法分析与实现(C/C++) 更多算法可以去看看我的算法专题： http://www.wutianqi.com/sfzt.html 以下是SPFA的代码模板： 1 2 3 4 5 6 [...]