翼若垂天之云

最小树形图就是给定一个有向图，求以某个给定顶点为根的有向生成树（也就是说沿着这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

Tags: 最小树形图, 算法

Related posts

RMQ问题
利用 Sparse Table 构造 Suffix Array
矩阵乘法
LCA问题
字符串匹配自动机

对于我这种人来说，如果想让我踏踏实实的进行一个长期计划，最好的办法就是把这个计划让全世界的人都知道。比如说我准备做USACO和SGU的时候，就专门各开了一个发布题解的blog，这样我做了多少题目老师、同学、朋友甚至父母每天都能看到，我也就一点不敢松懈了。现在USACO征程完成了，SGU之旅做了80+（窃以为Chapter I/II中最有价值的题目都做了），于是我又打算做SPOJ了。
SPOJ真是一个非常非常好的OJ，网站的架构和理念非常先进。超级无敌的多语言支持就无需赘述了。还有一些很贴心的功能，比如说它会保留你每次提交的源文件，可以自己下载自己以前的代码，而且若选择了邮件通知功能，还会把每次提交的代码作为附件发给你。另外像调整宽度、换肤、提供每题的PS/PDF等小细节都很令人赞叹。这的确是我看到的最完美的OJ系统，在上面做题的确非常舒服。
好了，说了这么多，只是为了督促自己努力做题。除了学些新算法（其实需要学的已经为数不多）以外，更重要的是训练自己的代码风格变得严谨，彻底改变以前那种狂提交的做题方式，提高一次AC率，顺便还能给这个题解很缺乏的OJ贡献一份尽量丰富的题解。考虑到我的blog已经着实不少，就不再为这个OJ新开blog了，请通过这个页面监督我的做题情况！

Tags: SPOJ

Related posts

No related posts.

近期必须要提高效率。用二至三天的时间详细记录时间表，以提高效率。每天早计划晚总结。
必须要做的是把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的题目很不错，对照着题目/题解欣赏下似乎很好。
效率，一定要注意效率。珍惜时间，绝对不启动浪费大块时间的娱乐计划。

Tags: NOI

Related posts

实时离散化：NOI2003 editor另解
ACM新手上路总结及感言
NOI计划，五月下
给正为4月26日奋斗的学弟学妹们

最近大部分人可能上不去OIBH。所以ioiforum的猫欢迎OIers前去讨论OI问题。据我所知，ioiforum是有神牛出没的。所以说若你有疑难问题希望得到指点，到那里发帖应该是个不错的选择。
地址：http://ioiforum.bytecool.com/
（本文为友情广告）

Tags: ioiforum

Related posts

No related posts.

最大权二分匹配问题就是给二分图的每条边一个权值，选择若干不相交的边，得到的总权值最大。解决这个问题可以用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

Tags: KM算法, 二分匹配, 算法

Related posts

求最大流的使用距离标号的最短增广路算法
平衡二叉查找树
字符串匹配自动机
虚二叉树
并查集