最小树形图就是给定一个有向图，求以某个给定顶点为根的有向生成树（也就是说沿着这N-1条有向边可以从根走到任意点），使权和最小。

解决这个问题有一个O(VE)的算法，是这样的：对于除根外的每个顶点，选择一条权最小的入边。如果选出来的V-1条边不构成环，则可以证明这些边就是满足要求的答案。如果存在环，则将环中的边收缩成一个顶点。设x是环中的点，y不是环中的点，v为新的顶点，w0为上一步中x选择的入边的权值，则原来的权值为w的边(x,y)变成权值为w的边(v,y)，原来的权值为w的边(y,x)变成权值为w-w0的边(y,v)。这时最小树形图的答案就是环的权值和加上收缩以后的图的答案。

为什么收缩了以后要减小权值呢？很简单，最小树形图需要每个顶点选一条入边，顶点x当前已经有入边了，如果以后再给收缩后的顶点x选择权值为w的（原来属于x的）入边，就意味着已经选择的那条权值为w0的入边可以去掉了，也就是说选择这条边的代价应该是w-w0，所以就做这样的修改。

不过如果不固定根，我还不太知道如何用同样的复杂度解决，谁写过请教教我。

（发现自己最近表达能力很差，这个文章说得清楚些。）

示例程序（TJU2248，用邻接矩阵写的，O(V^3)，比较简洁）：
tju2248.cpp

对于我这种人来说，如果想让我踏踏实实的进行一个长期计划，最好的办法就是把这个计划让全世界的人都知道。比如说我准备做USACO和SGU的时候，就专门各开了一个发布题解的blog，这样我做了多少题目老师、同学、朋友甚至父母每天都能看到，我也就一点不敢松懈了。现在USACO征程完成了，SGU之旅做了80+（窃以为Chapter I/II中最有价值的题目都做了），于是我又打算做SPOJ了。

SPOJ真是一个非常非常好的OJ，网站的架构和理念非常先进。超级无敌的多语言支持就无需赘述了。还有一些很贴心的功能，比如说它会保留你每次提交的源文件，可以自己下载自己以前的代码，而且若选择了邮件通知功能，还会把每次提交的代码作为附件发给你。另外像调整宽度、换肤、提供每题的PS/PDF等小细节都很令人赞叹。这的确是我看到的最完美的OJ系统，在上面做题的确非常舒服。

好了，说了这么多，只是为了督促自己努力做题。除了学些新算法（其实需要学的已经为数不多）以外，更重要的是训练自己的代码风格变得严谨，彻底改变以前那种狂提交的做题方式，提高一次AC率，顺便还能给这个题解很缺乏的OJ贡献一份尽量丰富的题解。考虑到我的blog已经着实不少，就不再为这个OJ新开blog了，请通过这个页面监督我的做题情况！

近期必须要提高效率。用二至三天的时间详细记录时间表，以提高效率。每天早计划晚总结。

必须要做的是把Linux装好，Emacs和Vim都试试。总结一下自己用Dev-C++时需要的全部功能，然后用某种编辑器全部替代了。GDB也可以试试，如果真的很爽的话就用Emacs了。Vim最无奈的就是编译了，感觉上比较好的解决方案还是写makefile，这样的话多Tab要搞清楚。

算法方面，一个必须要掌握的就是块状链表，考的可能性很大，所以说完全可以花一两天甚至更多时间仔细研究仔细实现，除了NOI2005那个题以外还得找别的练习一下。网络流再写一两遍relabel-to-front，感觉一下，有空的话写个HLPP也行，Dinic写不写似乎都没关系，毕竟距离标号已经写得很熟了。

平衡树是另外一个大重点，一定要多练些麻烦的题练熟了。把递归Treap和Buttom-Up Splay要练到十分钟/十五分钟能默写的程度。

字符串处理方面。Trie图的相应的那几道题目做了也就没什么需要多说的了。最好搞懂“扩展KMP”是什么东西。后缀数组，如果遇到了非得O(N)的题再考虑学Skew Algorithm，否则就把nlogn的好好掌握就行了。

做题的话，SGU应该在一周内告一段落。下一步就去SPOJ攻难题吧，也可以照着网上的题目推荐内容做些POJ/Ural之类的补充。另外发现TopCoder的题目很不错，对照着题目/题解欣赏下似乎很好。

效率，一定要注意效率。珍惜时间，绝对不启动浪费大块时间的娱乐计划。

最近大部分人可能上不去OIBH。所以ioiforum的猫欢迎OIers前去讨论OI问题。据我所知，ioiforum是有神牛出没的。所以说若你有疑难问题希望得到指点，到那里发帖应该是个不错的选择。

地址：http://ioiforum.bytecool.com/

（本文为友情广告）

最大权二分匹配问题就是给二分图的每条边一个权值，选择若干不相交的边，得到的总权值最大。解决这个问题可以用KM算法。理解KM算法需要首先理解“可行顶标”的概念。可行顶标是指关于二分图两边的每个点的一个值lx[i]或ly[j]，保证对于每条边w[i][j]都有lx[i]+ly[j]-w[i][j]>=0。如果所有满足lx[i]+ly[j]==w[i][j]的边组成的导出子图中存在一个完美匹配，那么这个完美匹配肯定就是原图中的最大权匹配。理由很简单：这个匹配的权值之和恰等于所有顶标的和，由于上面的那个不等式，另外的任何匹配方案的权值和都不会大于所有顶标的和。

但问题是，对于当前的顶标的导出子图并不一定存在完美匹配。这时，可以用某种方法对顶标进行调整。调整的方法是：根据最后一次不成功的寻找交错路的DFS，取所有i被访问到而j没被访问到的边(i,j)的lx[i]+ly[j]-w[i][j]的最小值d。将交错树中的所有左端点的顶标减小d，右端点的顶标增加d。经过这样的调整以后：原本在导出子图里面的边，两边的顶标都变了，不等式的等号仍然成立，仍然在导出子图里面；原本不在导出子图里面的边，它的左端点的顶标减小了，右端点的顶标没有变，而且由于d的定义，不等式仍然成立，所以他就可能进入了导出子图里。

初始时随便指定一个可行顶标，比如说lx[i]=max{w[i][j]|j是右边的点}，ly[i]=0。然后对每个顶点进行类似Hungary算法的find过程，如果某次find没有成功，则按照这次find访问到的点对可行顶标进行上述调整。这样就可以逐步找到完美匹配了。

值得注意的一点是，按照上述d的定义去求d的话需要O(N^2)的时间，因为d需要被求O(N^2)次，这就成了算法的瓶颈。可以这样优化：设slack[j]表示右边的点j的所有不在导出子图的边对应的lx[i]+ly[j]-w[i][j]的最小值，在find过程中，若某条边不在导出子图中就用它对相应的slack值进行更新。然后求d只要用O(N)的时间找到slack中的最小值就可以了。

如果是求最小权匹配，只需要把那个不等式反一下就行了。算法需要作出的改变是：lx的初值为所有临界边中的最小值，find中t反号。

示例程序(Ural 1076)：
ural1076.cpp

当在程序中使用滚动数组之类的优化手段时，一般我们会先写出不用滚动数组的程序，用小数据调试、验证后再将它改成用滚动数组实现。这时，你会如何实现这样的改动呢？好吧，请看看，使用C++，可以将滚动数组实现得多么优雅，如何将一个只改声明部分、不改实现部分就引入滚动数组的优化。

程序请见：http://ddsgu.yo2.cn/183.html

NOI2003的editor（文本编辑器）一题的标准解法是“块状链表”。这个东西我以前没有写过，怎么想都觉得无法将这个东西妥帖地实现。找到的一个这道题的C++程序竟然有三百多行，让我看得着实很恶心。这道题能不能不用这种很不优美的数据结构来解决呢？答案是肯定的！

我把我解决这个问题时使用的技术称为“实时离散化”。首先解释离散化，一种合适的理解就是将需要处理的序列中的某些连续的区间当作一个元素来操作，以减少总的元素数量。对于这道题而言，如果我们事先能够知道“在哪些字母的前后会插入一个区间”“在哪些字母的前后会有区间被删除”，把这些字母称为“关键字母”，用一个关键字母来代表它与它后面的所有非关键字母，就可以大大的降低时间复杂度了。因为INSERT和DELETE的操作总数不超过4000次，“关键字母”的总数也不会超过4000*2个，这样就相当于所有的插入删除操作都在最多8000个（而非2000000个）元素组成的串上进行，当然就会很快了。问题是，我们无法在一个字母被插入时判断出它是否会在将来成为“关键字母”，也就是说，无法像某些题目一样只做一次初始的离散化，我们的“离散化”必须是“实时”的，也就是，必须实时的维护可以被一同处理的区间。

听上去有点玄妙，其实很简单。用一个很长的字符数组保存曾经被插入的所有字符串，当前正在编辑的文本用一个区间的数组来表示，每个区间代表它在前述字符数组中的位置。当需要在某个区间的中间插入时，只需按照这个被插入的位置将这个区间分裂成两个，再在两个新形成的区间的中间插入就可以了。同样，删除时也只需要按照需要被删除的文本两端将它们所在的区间分裂成两个，然后删除连续的若干个区间就可以了。设修改操作一共做了M次，则任何时候的区间总数不会超过2M个，所以每次操作的时间复杂度都是O(M)，所有修改操作的总时间复杂度是O(M^2)，而且常数很小，由于M<=4000，是完全可以承受的。INSERT和DELETE都实现了，GET也很好实现，挨个输出就行了，PREV和NEXT更是常数时间而已，最多可达到50000次的MOVE呢？如果每个MOVE的复杂度也都是O(M)似乎会有超时的危险。注意到这样一个明显的事实：若有连续的MOVE操作，只需要做最后一次的操作即可。经过这样的处理，需要实际做的MOVE操作大约也只是O(M)的级别。

对于这类在序列上进行添加、删除、反序等修改的题目来说，设修改操作有M次，序列的最大长度为N，块状链表的复杂度是O(M*N^0.5），“实时离散化”的复杂度是O(M^2)或者O(M^2+N)，可见它在很多情况下是很有代替块状链表的可能的。对于某些题目而言，我认为它是相对于块状链表的一个更高层的抽象，所以编程要简单优雅很多（我的堆砌着大堆短函数的拖沓程序用了156行，其中核心的部分仅有不到100行），也不失效率。对于本题来说，我的程序可以P4 2.oG的电脑上最大数据1.6s左右，是可以AC的。但是，“实时离散化”还是不能完全代替块状链表，比如说当M与N同阶的时候就会退化成O(N^2)（因为已经失去了离散化的意义了），而块状链表仍然保持着O(N^1.5）。

示例程序：
editor.cpp

一会儿要给高一学信息学奥赛的学弟学妹们讲一节课，讲我去年在各种模拟赛中的一些原创题目。其实，别说“讲课”，连号称“讲座”的东西我也是做过的。可是……为何此刻我如此紧张呢？有些人有些事该放开吧……

21:23 update：讲完了。除了幻灯片上有一处字母打错了的低级错误以外，没出什么大的失误。不过那些学弟学妹们一脸迷茫的样子……我确定有人完全没听懂。可是……

第一题是计算几何题，我的构图是这样的：每条线段给最终的图贡献几个顶点，两端点、所有交点、离终点最近的点，出自同一条线段的点互相之间的权值为距离，出自不同线段但事实上重合的点（比如说交点事实上出现两次）之间权值为零，其他权值均为正无穷，起点也在图中，在哪条线段上就与这条线段贡献的所有顶点连边。然后做一次Dijkstra，求出所有点到起点的距离，最后按照步行距离为第一关键字，行驶距离为第二关键字找到最小值即可。需要用到的计算几何内容有：判相交、求交点、判点在线段上、求点与线段的最近点，有些东西我甚至是现学的，好在时间充裕。

第二题我比较晕，如果是完全合法的robots.txt我的程序肯定能解析，但最后结果到底是怎么样还得看数据。我忽略了所有的大小写，还忽略了所有’/'与’\'的区别。一开始竟然忘记处理注释，还好最后加上了。

第三题求较优解，我的算法是一次贪心加一次贪心的调整。首先选择能够对整体尽量符合的关键字，然后根据最不匹配的那个人的情况进行一些调整。加了卡时，应该能保证每个点都有分吧。本来想对于所有的字符串进行hash来判重，但又觉得太不保险，就采用了顺序比较来判重的方法，为了保证不超时，如果当前的词汇太多的话就忽略剩下的所有词。考完了以后才想到，其实蛮可以使用hash进行第一步的判重，然后再实际判重，这样会大大提高效率，肯定就不需要采用那个可能使解的质量大打折扣的剪枝了。或者使用STL里面的map也可以呀，都是学OI学的把这些若干个月前还熟稔于心的东西都忘完了。

第四题还是较优解，算法是每次进行BFS，每个维修队都向最近的公司去修。一个剪枝是当前已经完全没有可能修复的公司就放弃（在程序中就是当作已经完全修复处理）。还是用卡时的手段来保证有分，也就是快超时了就全部REST。

题目还是不错的，第一题考察算法基本功（但为什么就考到了我最薄弱的计算几何……），第二题考察工程功底（这点我目前还相当差……），第三题和第四题都是不错的算法设计题。我估计第一题和第四题会分比较多，第二题完全看数据了，第三题多少会得点分。目前进复赛的期望比考前高了一些。

我就是这么矫情，喜欢一个歌手时，便会害怕听到他的新碟。因为生怕找不到当初的激动，害怕那种好友不再般的失落，所以才会将Linkin Park五月的新碟Minutes to Midnight拖到今日才听。可是，无意的谶言还是应验了。我何会想到一时翘楚的Linkin Park有朝一日也会变得这般平和无力，甚至波澜不惊。卖力的吉他只是掩饰，鼓点却已懈怠，剩下单薄的人声，哪还有半点当年睥睨天下的气象。我只能无奈的承认，曾让我那样喜欢的Linkin Park已然江郎才尽，剩下的只是媚俗。可还是不能太过责怪他们吧，他们不过是游走于音乐与金钱之间的几个青年而已。他们曾引领时代，却终究被时代裹挟而不能自己。失去了Linkin Park的时代，我们仍然不缺好音乐听。也许，这就是这个时代既最好又最坏的含义吧。