algorithm - 边成本为 1，顶点成本为 2 的最小成本算法

Question

我正在尝试找出适用于以下情况的算法:我想在无向图上运行最小成本算法。边有一个与之相关的成本，顶点有 2 个成本与其中一个相关。这就是它变得有点棘手的地方。我必须选择与顶点相关的 2 个成本之一。如果我选择 cost1，顶点将是类型 1，如果我选择 cost2，顶点将是类型 2。如果顶点是不同类型，则它们只能被视为由边连接。大多数情况下，为顶点选择最低成本是合乎逻辑的，但是根据与其关联的边的成本及其相邻顶点的类型，您更愿意为顶点选择最高成本，结果在较小的总成本上。非常感谢任何建议，例如我应该尝试应用哪种算法或什么方法。

Here is a link to a simple example of what I am trying to achieve .该解决方案的成本为 57，这是该图的最低可能成本。

编辑:拼写。

Answer 1

您描述的问题可以简单地转换为最小切割问题，然后用 Stoer-Wagner algorithm 解决.再创建两个顶点，每个顶点都有到所有其他顶点(彼此除外)的边。一方面，边成本取自相应顶点的成本；另一方面，来自他们的成本。现在找到最小割；这将在两个新节点之间进行切割，并将原始顶点划分为 type1 和 type2。

编辑:如果(原始)边成本与顶点成本相比足够高，您可能会在同一分区中得到两个新顶点。为防止这种情况发生，请向添加到新顶点的所有边添加一个大的相等成本(大于所有其他边的总和)。