Facebook编程挑战 - ByteLand

Question

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

你是敌国的统治者，并且制定了摧毁拜特兰的计划。你的计划是摧毁Byteland的所有道路，破坏所有的沟通。如果你攻击任何一条路，来自两条连接城市的军队都是为了防守。你意识到如果军队A和B都有士兵防御任何道路，你的攻击就会失败。

所以你决定在实施这个计划之前，你会攻击一些城市并击败位于城市的军队，使你的计划成为可能。然而，这是相当大的难度。你估计击败位于城市的军队将占用大量的资源。你的目标现在是决定攻击哪个城市，使你的成本是最小的，没有路应该从两军A和B.

被保护----请告诉我，如果这种做法是正确的----

我们需要根据摧毁城市所需的资源对城市进行排序。对于每个城市，我们需要询问以下问题：

1）删除了以前的城市是不是会导致可以破坏Byteland的州？

2）它连接任何道路吗？

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

如果所有这些条件都满足，我们将继续朝着摧毁城市和记录迄今为止所遭遇的总成本，并确定这个城市的破坏将导致Byteland的整体破坏。

由于城市按照成本增加的顺序排列，我们可以在任何地方找到所需的删除组。

Answer 1

你只需要关心以不同的军队连接两个城市的道路 - A和B或B和A之间的链接之间的联系，让我们删除从A到A或B的所有链接B.

你想找到一组点，使得每个链接上至少有一个点，这是一个最小权重顶点覆盖。在任意图上，这将是NP完全的。但是，您的图只有类型A的节点链接到类型B的节点，或者相反 - 它是具有这两种类型的节点作为双方的双向图。所以，你可以通过使用一种算法寻找最小重量顶点找到一个最小重量顶点覆盖上二部图覆盖。寻找这个，我发现例如http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-854j-advanced-algorithms-fall-2008/assignments/sol5.pdf

Answer 2

mcdowella，

但顶点具有成本，对他们的最低点覆盖不会产生正确的顶点删除。设想2个顶点（军队）指向第三个（B）。前两个顶点每个花费1，其中第三个花费5个。最小顶点覆盖将返回第三个顶点覆盖 - 但移除第三个顶点花费比以成本1 + 1移除两个节点更多。

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