Monthly Archives: January 2010

POJ 3026 —— Borg Maze

Posted on January 31, 2010 by chenyajun

http://hi.baidu.com/archersfate/blog/item/8884b00898870fa62fddd44c.html http://blog.163.com/lu_jian_bin2006@126/blog/static/48789281200987111046892/

Posted in POJ | Leave a comment

POJ 1161 —— Walls

Posted on January 31, 2010 by chenyajun

题目太长，收藏了，转自 http://hi.baidu.com/archersfate/blog/item/4fbc57222e8d124dad34dea3.html

Posted in POJ | Leave a comment

POJ 2949 —— Word Rings

Posted on January 31, 2010 by chenyajun

这道题的题意并不难理解，就是找出图中的一个环，使得环上边的平均权值最大。 综合了两种常见的问题：字符串的接龙以及平均值的最优化问题。对于前者，我们可以采取把单词看成边，把首尾字母组合看成点的方法。例如对于单词 ababc 就是点”ab”向点”bc”连一条长度为 5 的边。这样问题的模型变得更加清晰，规模也得到减小。那么原问题就可以转化成在此图中找一个环，使得环上边权的平均值最大。

Posted in POJ | Tagged , | Leave a comment

POJ 3723 —— Conscription

Posted on January 24, 2010 by chenyajun

求出最小生成树，将每个人看成一个点，若 x 与 y 有关系 d，则看成有一条权值为 10000-d 的边，由于M和N的范围很大（1 ≤ N, M ≤ 10000）所以采用邻接表来存储图，然后求最小生成树。 对于孤立点，则是必选的。图不一定是完全连通的，有可能要进行几次最小生成树才行。 http://hi.baidu.com/yxdark/blog/item/810e04c301a2d23de4dd3b4c.html

Posted in POJ | Tagged , | Comments Off

数据结构与算法复习（14）—— 二分匹配与路径覆盖

Posted on January 19, 2010 by chenyajun

二分匹配常见的集中情形：最大匹配，最佳匹配。 最小覆盖： 最小覆盖要求用最少的点（X 集合或 Y 集合的都行）让每条边都至少和其中一个点关联。可以证明：最少的点（即覆盖数）＝ 最大匹配数，这就是所谓 Konig 定理。 最小路径覆盖：用尽量少的不相交简单路径覆盖有向无环图 G 的所有结点。解决此类问题可以建立一个二分图模型。把所有顶点 i 拆成两个：X 结点集中的 i 和 Y 结点集中的 i',如果有边 i->j，则在二分图中引入边 i->j'，设二分图最大匹配为 m,则结果就是 n-m。 最大独立集问题：在 N 个点的图 G 中选出 m 个点，使这 m 个点两两之间没有边．求 m 最大值．如果图 G 满足二分图条件，则可以用二分图匹配来做．最大独立集点数 = N - … Continue reading →

Posted in 数据结构与算法 | Comments Off

Berkeley DB 锁的一个小例子

Posted on January 14, 2010 by chenyajun

关于 Berkeley DB 锁的一个小例子： 留此备注，免得忘了。 每个 thread of control 应该去获得自己独立的 DB_LOCK，这个好像不能共享； DB_ENV->lock_id 返回的是 BerkeleyDB 分配的锁持有者 ID（lockerid），而不是锁的 ID，用于标识上锁者；这个 ID 是可以循环使用的（就像进程号），基本不会用光。db_stat -CA 可以看到最近分配的上锁者 ID。也可以让你看到哪个上锁者锁住了哪个对象；锁系统统计等等。 要锁住的对象应该是全局可以看到的；

Posted in Berkeley DB | Comments Off