2

ByteLand Byteland由N个城市组成，编号为1..N。有 M 条道路连接几对城市。有两个陆军师，A和B，保护王国。每个城市要么由陆军师 A 或由陆军师 B 保护。  

你是一个敌国的统治者，并制定了摧毁 Byteland 的计划。你的计划是摧毁 Byteland 的所有道路，中断所有通信。如果你攻击任何一条道路，这条道路连接的两个城市的军队都会前来防御。你意识到如果有来自 A 军和 B 军的士兵保卫任何一条道路，你的攻击就会失败。  

所以你决定，在执行这个计划之前，你会攻击一些城市并击败位于城市的军队，以使你的计划成为可能。然而，这要困难得多。您估计击败位于城市的军队将占用ci数量的资源。你现在的目标是决定攻击哪些城市，以使你的成本最小，并且不应该保护任何道路免受军队 A 和 B 的攻击。  

----请告诉我这种方法是否正确----

我们需要根据摧毁城市所需的资源对城市进行分类。对于每个城市，我们需要提出以下问题：

1）删除之前的城市不会导致可以摧毁Byteland的状态吗？

2）它连接任何道路吗？

3）它是否连接由不同城市武装的任何道路？

如果所有这些条件都成立，我们将着手摧毁这座城市并记录到目前为止所产生的总成本，并确定摧毁这座城市是否会导致 Byteland 的整体毁灭。

由于城市是按照所产生成本的递增顺序排列的，因此我们可以在找到所需删除集的任何地方停止。

4

2 回答 2

2

You need only care about roads that link two cities with different armies - links between A and B or links between B and A, so let's delete all links from A to A or B to B.

You want to find a set of points such that each link has at least one point on it, which is a minimum weight vertex cover. On an arbitrary graph this would be NP-complete. However, your graph only ever has nodes of type A linked to nodes of type B, or the reverse - it is a bipartite graph with these two types of nodes as the two parties. So you can find a minimum weight vertex cover by using an algorithm for finding minimum weight vertex covers on bipartite graphs. Searching for this, I find e.g. http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-854j-advanced-algorithms-fall-2008/assignments/sol5.pdf

于 2013-01-18T14:09:39.727 回答
1

麦克多维拉，

但是顶点对它们来说是有代价的，并且最小的顶点覆盖不会产生要删除的正确顶点。想象一下 2 个顶点（A 军队）指向第三个（B）。前两个顶点每个花费 1，第三个花费 5。最小顶点覆盖将返回第三个 - 但移除第三个顶点的成本高于移除成本为 1 + 1 的两个节点。

我们可能需要一些修改版本的最小顶点覆盖。

于 2013-07-10T17:12:45.030 回答