c++ - 顶点子集

Question

我有一个家庭作业问题，我不知道如何解决它。如果您能给我一个想法，我将不胜感激。

这就是问题所在：“给定一个具有 N 个顶点和 N 个边的连通无向图。每个顶点都有一个成本。您必须找到一个顶点子集，以便子集中顶点的总成本最小，并且每条边都与子集中的至少一个顶点相关。”

先感谢您！

PS：我长期以来一直在寻找解决方案，我提出的唯一想法是回溯或二分图中的最小成本匹配，但是对于 N = 100000，这两个想法都太慢了。

Answer 1

这可以使用动态规划在线性时间内解决。

具有 N 个顶点和 N 条边的连通图恰好包含一个环。从检测这个循环开始（借助深度优先搜索）。

然后删除此循环中的任何边缘。与这条边相连的两个顶点是u和v。在这个边缘去除之后，我们有一棵树。将其解释为根为u的有根树。

这棵树的动态规划递归可以这样定义：

• w ₀ [k] = 0（对于叶节点）
• w ₁ [k] = vertex_cost（对于叶节点）
• w ₀ [k] = w ₁ [k+1]（对于有一个后代的节点）
• w ₁ [k] = vertex_cost + min( w ₀ [k+1], w ₁ [k+1]) （对于有一个后代的节点）
• w ₀ [k] = sum( w ₁ [k+1], x ₁ [k+1], ...) （对于分支节点）
• w ₁ [k] = vertex_cost + sum(min( w ₀ [k+1], w ₁ [k+1]), min( x ₀ [k+1], x ₁ [k+1]), .. .)

这里k是节点深度（到根的距离），w ₀是当w不在“子集”中时从节点 w 开始的子树的成本，w 1_是当 w 是时从节点 w 开始的子树的成本在“子集”中。

对于每个节点，只需计算两个值：w ₀和w ₁。但是对于循环中的节点，我们需要 4 个值：w _i,j ，如果节点v不在“子集”中，则i=0，如果节点v在“子集”中，则 i=1 ，如果当前节点不在“子集”内，如果当前节点在“子集”内，则 j=1。

“子集”的最优成本被确定为 min( u _0,1 , u _1,0 , u _1,1 )。要获取“子集”本身，请将反向指针与每个子树成本一起存储，并使用它们来重建子集。

Answer 2

由于边的数量对相同的顶点数量是严格的，所以它不是常见的顶点覆盖问题，它是 NP-Complete 的。我认为这里有一个多项式解决方案：

1. N 个顶点和 (N-1) 条边的图是一棵树。您的图有 N 个顶点和 N 个边。首先找到导致循环的可怕边缘并将图制作成树。您可以使用 DFS 来查找循环 ( O(N))。删除循环中的任何一条边都会生成一棵可能的树。在极端情况下，你会得到 N 棵可能的树（原始图是一个圆圈）。

2. O(N)对每棵可能的树 ( )应用一个简单的动态规划算法 ( O(N^2))，然后找到成本最低的那棵。