SHENXN's BLOG

Purdue University
Computer Science, Math

Xiaonan Shen's avatar Xiaonan Shen

[POJ2195]Going Home(KM算法)

就是一道KM的模板题,而且建图已经非常显然了。关于KM算法: KM算法流程: (1)初始化可行顶标值 (2)用匈牙利算法寻找完备匹配 (3)若未找到完备匹配则修改可行顶标的值 (4)重复(2)(3)直到找到相等子图的完备匹配为止上述内容转自:二分图匹配算法总结(phoenixinter),更详细的讲述详见原文。     Read more

Xiaonan Shen's avatar Xiaonan Shen

[POJ2104]K-th Number(主席树)

终于下定决心开始学主席树了,先找了一道不带修改的区间第K大做。关于带修改的区间第K大,参见我的下一篇博客 [BZOJ1902][ZOJ2112]ZJU2112 Dynamic Rankings(树状数组 + 主席树) 主席树其实就是一种可持久化的线段树,是函数式编程的一个很经典的应用(另外的话,我就只知道FANHQ_TREAP了)。主要思想是在对线段树的节点进行修改的时候,不改变原节点,而是新开一个节点并链到数中。     Read more