读到此题第一反应是似曾相识, poj1466。

两题都来自一次比赛，关键是输入无比的相似，因为那题关系，立刻想到了二分图匹配。

再想想其间的关系：

此题所求是最小顶点覆盖数。而二分图Konig定理：对二部图，最大匹配数=最小顶点覆盖数

最为关键的是，任何“树形”图结构都能很轻易的转换成二分图(1466那种特殊图也可以)。

这样一来就可以用匈牙利算法来求解。


看到不少留言说采用贪心，大概思路是每次选取边数为1的节点p,然后覆盖与p相连的点q的所有边。

我写了一个，通过了。 又想到了对于二分图最大匹配也可以采用贪心，策略与上相同。

对于任意一个二分图n*m, 都可以转换成一个 N*N(N=n+m) 的图, 反之则不然。


结论：

对于任意无向图G，都可以采用[贪心]来求解[最小顶点覆盖数]，(贪心的正确性有待考证)；

对于可以转换成二分图的G，可以采用[匈牙利算法]来求解[最小顶点覆盖数]，根据Konig定理；

对于可以转换成树形图的G，可以采用[树形DP]来求解[最小顶点覆盖数]，

DP关系：根树的值=Min(覆盖时，不覆盖时),覆盖时=1+Σ子树的值, 不覆盖时=Σ子树覆盖时；

作用范围由上至下呈包含关系，这道题目满足第三种情况，因此三种算法都可以采取。



而对于第一种情况的贪心算法，当图中存在环时，情况就有些不同了，我以前写过一个程序，
采取的策略是：当贪心进行中存在环时，从中任意选择一个点进行覆盖，环就被拆解了， 这似乎是正确的。

• Re:一点点联想,关键字: 二分图 (500) tzkq 2010-07-11 06:06:53