刚才用上述贪心的方法做了1466，也就是第二种二分图的情况（含环）。

结果是错误的， 证明了在存在环的时候，用上述贪心求解[最小顶点覆盖数]是有问题的。

但是，对于二分图求解[最大匹配数]，可以采用另外一种贪心，策略:

1.当图中存在唯一边时，也就是存在一个度数为1的节点时，该边一定可以选取(一次匹配)。

2.当图中只剩下环时， 任意选取一边作为一次匹配。

3.重复上面步骤，直到不存在边或环。


已经用这种贪心策略通过了几道二分图最大匹配的题，虽然正确性仍待证明。

而原先那种只能进行对树形图求解[最小顶点覆盖数]的贪心，就是这种贪心的第一步的反复。


至于对于任意图求解[最小顶点覆盖数]，至此仍未有一个良好的算法。


刚刚看了http://zh.wikipedia.org/zh-cn/%E8%A6%86%E7%9B%96_%28%E5%9B%BE%E8%AE%BA%29

任意图的情况下，这是一个NP完全问题，我不知道npc是啥米(Non Player Character非玩家控制角色?)，看起来似乎是一个大麻烦。