c++ - 等价集中的分区

Question

我有一个简单的、无方向的树T。我应该找到一个命名的路径A和另一个命名的路径B，A并且B没有公共顶点。目的是最大化Len(A)*Len(B).

我认为这个问题类似于分区问题，除了在分区问题中你有一个集合，但在这里你有一个等价集。解决办法是找到两条不相交的路径Len(A) ~ Len(B) ~ [n-1/2]。这是正确的吗？我应该如何实现这样的算法？

Answer 1

我认为如果路径长度只是路径中链接的数量（因此链接没有权重），那么动态编程解决方案几乎是易于处理的。

从叶子向上工作。在每个节点上，您需要跟踪限制在该节点处具有根的子树的最佳解决方案对，并且对于每个 k，具有在该节点终止的长度为 k 的路径和最大长度的第二个路径的最佳解决方案在该节点下方的某个地方并且不接触路径。

给定节点的所有后代的此信息，您可以为该节点生成类似的信息，然后按照自己的方式到达路由。

如果您考虑实际上只是一行节点的树，您会看到需要这么多信息。一行节点的最佳解决方案是将其一分为二，因此，如果您仅在该行的长度为 2n + 1 时制定了最佳解决方案，那么您将没有长度为 2n 的行所需的构建块+ 3。

Answer 2

首先。我认为您以错误的方式看待这个问题。据我了解，您有一个与图表相关的问题。你所做的是

1. 建立一个最大生成树并找到长度 L。
2. 现在，你说两条路径不能有任何共同的顶点，所以我们必须删除一条边来归档它。我假设图中的每条边的重量都是 1。因此，在删除一条边后，两条路径 A 和 B 的总和为 L-1。现在的问题是您必须删除一条边，以使 len(a) 和 len(b) 的乘积最大化。您可以通过移除 L 的 et most 'middel' 中的边缘来做到这一点。为什么，问题与优化具有固定周长的矩形的面积相同。可以在此处找到有关该主题的简短 youtube 视频。

请注意，如果您的边权重不等于 1，那么您将遇到一个更难的问题，因为可能存在不止一个最大生成树。但是您也许可以以不同的方式拆分它们，如果是这种情况，请给我回信，然后我会考虑解决方案，但是我手头没有。

祝你好运。