字节地 Byteland 由 N 个城市组成，编号为 1..N。有 M 条道路连接一些城市对。有两个军团，A和B，负责保护王国。每个城市要么由陆军师 A 保护，要么由陆军师 B 保护。
你是敌方王国的统治者，并制定了一个摧毁拜特兰的计划。你的计划是摧毁 Byteland 的所有道路，中断所有通讯。如果你攻击任何一条道路，该道路所连接的两个城市的军队都会前来防御。你意识到，如果有 A 军和 B 军的士兵防守任何一条道路，你的攻击就会失败。
所以你决定在执行这个计划之前，你将攻击一些城市并击败位于城市中的军队以使你的计划成为可能。然而，这要困难得多。您估计击败位于 i 城市的军队将占用 ci 资源。你现在的目标是决定攻击哪些城市，以便你的成本最小，并且没有一条道路可以同时受到 A 和 B 军队的保护。
----请告诉我这个方法是否正确----
我们需要根据摧毁城市所需的资源对城市进行排序。对于每个城市，我们需要提出以下问题:
1)删除先前的城市是否不会导致一个可以摧毁Byteland的状态？
2)它连接任何道路吗？
3)它是否连接任何由不同城市武装的道路？
如果所有这些条件都成立，我们将继续摧毁这座城市并记录到目前为止所产生的总成本，并确定摧毁这座城市是否会导致 Byteland 的全面破坏。
由于城市是按照所产生的成本的升序排列的，因此我们可以在找到所需删除集的任何地方停止。
最佳答案
您只需要关心连接两个拥有不同军队的城市的道路 - 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
关于Facebook 编程挑战赛 - ByteLand，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/14392354/