您好，谁能提示一下这个问题的潜在图问题是什么？
https://icpcarchive.ecs.baylor.edu/external/64/6450.pdf
我个人是这样想的:
通过递减边数对图的节点数进行排序。然后选择最上面的一个。之后忽略此顶部节点连接到的所有节点。然后选择下一个。
第一个测试用例
答案是 1，因为图是完全连接的，选择任何节点都将确保覆盖所有其他节点。
第二个测试用例
我们可以选择节点 5(这将覆盖节点 1、2 和 4)。然后我们可以选择节点 3。这样所有节点都被覆盖了。
问题是这种方法在我看来只是编造的一种。这不是任何图形算法。
如果有人能给出提示就太好了。谢谢。
VVV
最佳答案
这是 Dominating Set问题，这是 NP 难的，所以除非 P = NP，否则它没有多项式解。
请注意 n < 20，幸运的是我们仍然可以足够快地解决它。对于每个用户 0 ≤ i < n，让我们用位掩码 b(i) 表示其邻域，其中 n 位已设置所有位表示从 i 可通过长度 ≤ 1 的路径到达的用户。我们可以在 O(n²) 中预先计算 b(i)。
让我们将 f(i,m) 定义为达到由位掩码 m 表示的所有用户所需的最小用户数，仅在用户墙上发帖索引 ≤ i。我们可以使用以下算法计算 f:
f(i,m) = ∞ for all i, m
f(0, 0) = 0
f(0, b(0)) = 1
for i = 1 to n - 1:
for m = 0 to 2^n - 1:
f(i, m) = min(f(i, m), f(i - 1, m))
f(i, m | b(i)) = min(f(i, m | b(i)), f(i - 1, m) + 1)
答案是f(n - 1, 2^n - 1)。运行时间:O(n * 2^n)
关于algorithm - 图算法思想，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/22154979/