8

我们得到一个图 G(V,E)，它有 N 个节点（编号从 0 到 N-1）和正好 (N-1)个双向边。

图中的每条边都有一个正成本 C(u,v)（边权重）。

整个图是这样的，在任何一对 Nodes 之间都有一条唯一的路径。

我们还给出了一个节点号列表L，炸弹放置在该列表 L 上。

我们的目标是从图中损坏/移除边缘，这样，在从图中损坏/移除边缘之后，炸弹之间就没有联系了——

也就是破坏后，任意两颗炸弹之间都没有路径。

损坏 Edge(u,v) = Edge weight(u,v)的成本。

因此，我们必须破坏这些边缘，以使总破坏成本最小。

例子：

Total Nodes=N=5 
Total Bomb=Size of List L=3

List L={2,4,0}//Thats is at node number 2,4 and 0 bomb is placed...

Total Edges =N-1=4 edges are::

u v Edge-Weight

2 1 8

1 0 5

2 4 5

1 3 4



In this case the answer is ::
Total Damaging cost =(Edge Weight (2,4) + Edge Weight(0,1))
           =5+5=10.

So when we remove the edge connecting node (2,4),
and the edge connecting node (0,1) ,there is no connection left 
between any pair of machines in List {2,4,0};

Note any other,combinations of edges(that  we damaged ) to achieve the
target goal ,needs more than 10 unit cost.

在此处输入图像描述

Constraints::
N(ie. Number of Nodes) <= 100,000
ListSize |L|(ie. Number of Bombs) <= N
1 <=Edge cost(u,v) <= 1000,000

我做了什么？

直到现在，我还没有找到任何有效的方法:(。

此外，由于节点N的数量是 ，边的数量是准确N-1的，并且整个图是这样的，任何一对节点之间都存在唯一路径，我得出的结论是该图是一个TREE。

我试图修改 Kruskal 算法，但这也对我没有帮助。

谢谢！

4

6 回答 6

4

我认为修改后的 Kruskal 是通往这里的路。

取图 G'=(V', E'), V'=V, E'={}。以成本的非递增顺序对 E 中的边进行排序。现在，对于 E 中的每条边，将其添加到 E' 中，当且仅当它不连接两个组件，这两个组件都具有带有炸弹的顶点。结果是 EE' 成本的总和。

编辑：

在您的示例上运行它。

最初，我们的边集是空的 {}，我们将边按非升序排序 [(1, 2), (0, 1), (2, 4), (1, 3)]

因此，一开始，我们的图表由 5 个不连贯的组件组成。

(1, 2) 的成本为 8，并且它所连接的组件中只有一个具有炸弹。所以我们将它添加到 E'。E'={(1, 2)} 我们有 4 个分量。

下一个最高成本边是 (0, 1)，成本为 5。但是两个组件都有炸弹，所以不要添加这个边。

下一个是 (2, 4)。这也连接到带有炸弹的组件，所以我们也跳过它。

最后，最低成本边是 (1, 3)。由于它的一个组件（仅包含节点 3）没有炸弹，我们将它添加到 E'。

这给了我们 E' = {(1,2), (1, 3)}。

我的理由是，我们尝试在成本较低的边缘之前添加成本较高的边 - 这确保在原始节点中带有炸弹的节点之间的任何路径中，除了最低成本之外的所有边都将被添加。

于 2012-06-19T09:20:01.230 回答
2

我认为这可以在线性时间内完成。

将树根植于某个顶点，然后从自下而上遍历开始。

从一些叶子开始。如果没有炸弹，切掉叶子并继续前进。如果有炸弹，您必须在通往这片叶子的路径上切割一个边缘。向上传播有关最便宜边缘的信息。

然后当你在内部顶点时，你有这种可能性：如果顶点有炸弹，下面有一些炸弹，切掉所有这些炸弹的最便宜的路径。如果没有炸弹并且下面只有一颗炸弹，则传播有关最便宜路径的信息。如果下方有更多炸弹，则除最昂贵路径的炸弹外，将所有炸弹都砍掉。

于 2012-06-19T09:48:19.093 回答
2

这就是树中的多路切割问题。它可以通过简单的动态规划在多项式时间内求解。参见 Chopra 和 Rao：“ On the multiway cut polyhedron ”，Networks 21(1):51-89, 1991。

于 2012-06-19T10:40:48.837 回答
1

这是我的假设：

图G是一棵树。因此，任何两个节点之间只有一条路径。

假设有L Red（炸弹）节点和VL White（非炸弹节点）。该解决方案需要将 G 划分为 L 个子树的森林。这需要移除最少的L-1条边。

每个被移除的边缘都必须位于两个 Red 节点之间的路径上。

A. 修剪树 G 以删除所有不参与两个红色节点之间路径的边。

  1. 从考虑中删除白色叶节点（和入射边缘）。
  2. 重复#1，直到修改后的图中没有白色叶子节点。

B.在（A）之后，图中剩下的所有边都是边，它们形成了两个红色节点之间的路径。

选择这棵树中权重最小的边。这将产生两棵子树，每棵树至少包含一个红色节点。

C.如果 B 中创建的每个子树包含多个红色节点，则返回步骤 A。

这是 O(V log V) （|E| 是 |V| -1 ）。

于 2012-06-20T20:31:19.840 回答
0

我认为以下建议应该有效：

  • 1）从炸弹开始，在你的例子中，我从：0
  • 2）创建所有相邻节点的路径。所以，带着所有的关系，和他们一起开始一条路。在您的示例中，它将开始一条路径：0 -> 1.
  • 3）如果你在路径上击中另一个炸弹，你会以最低的成本移除边缘。在示例中，我们没有击中炸弹，所以我们继续第 2 步。
  • 3A) 任何路径上都没有炸弹。继续步骤 2 并使用新的相邻节点扩展路径。在您的情况下，将创建一个新路径：1 -> 3. 现有的将被扩展：0 -> 1 -> 2
  • 3B）在路径上发现炸弹。走找到炸弹的路径，去掉成本最低的边。在您的示例中，路径0 -> 1 -> 2包含炸弹 (2)。因此，我们删除与成本 5 的关系。从“待办事项”中删除路径，并在最后到达的节点（2 和 3）上继续执行步骤 2。

最后你应该只遍历每个节点一次。如果我没记错的话，复杂度应该是 O(n log n)

于 2012-06-19T09:27:33.747 回答
0

http://www.cs.ust.hk/mjg_lib/Classes/COMP572_Fall06/Notes/Tree_Multicut.ps

有算法的描述。

后记文件的Google HTML 版本

==========================================

http://dspace.mit.edu/bitstream/handle/1721.1/5394/OR-308-95.pdf?sequence=1

k = 2 的情况并不是多路割问题的唯一多项式可解实例。Lovdsz [12] 和 Cherkasskij [3] 表明，当 ce = 1 Ve EE 且 G 是欧拉时，多路割问题是多项式可解的。Erdos 和 Sz6kely [8] 表明，当底层图 G 是一棵树时，多路切割问题的推广是多项式可解的。达尔豪斯等。人。[7] 已经表明，对于平面图上的固定 k，该问题是多项式可解的。

昨晚我写了一个简单的基于贪心算法的解决方案，其中包括删除不在两个红色（终端）节点之间的路径上的节点，然后选择最小的权重节点，然后在子树上重复该过程。我删除了它，因为进一步阅读表明问题是NP。但是这个参考表明有一个多项式解决方案......

于 2012-06-20T08:08:19.217 回答