graph - 给定一个表示 n 个元素之间成本的邻接矩阵，我如何将 n 个元素分成 k 个组？

Question

给定 n 个元素之间的成本，其中 cost[i][j] 表示元素 i 和 j 之间的成本，我们需要将 n 个元素分成 k 个非空组，这样如果 2 个元素属于同一组，则对变为 0。给定划分，令 M 为不属于同一组的 2 对的最小成本。我需要找到最大可能的M。（划分没有给我们，我们需要找到最佳划分，然后找到最大可能的M）

我想对所有 cost[i][j] 进行排序，然后对其进行二进制搜索。假设我们在排序数组中的位置 x，其中成本为 M，它表示 (i,j) 之间的一条边。我们假设它是最大可能的 M。所以我们知道第 i 个元素和第 j 个元素需要在不同的组中。然后我们从第 i 个元素 bfs 并添加所有成本小于当前 M 的相邻元素。这将在当前组中。我们继续 bfsing，直到我们用完该组中的元素。然后我们移动到下一个组并从第 j 个元素再次执行 bfs。如果我们遇到一个已经在前一个组中但成本低于 M 的元素与当前组中的一个元素，我们要么返回 false，要么尝试合并两个组。这是我不确定的部分

例如，如果 n = 3, k = 2 且 cost[1][2] = 17,cost[2][3] = 15,cost[1][3] = 16

我们可以将元素 1 放在第 1 组中，将元素 2 放在第 2 组和第 3 组中。在这种情况下，最大 M 将为 min(cost[1][2],cost[1][3]) = 16

这是可以做到的最好的

标签： graphdynamic-programmingbinary-search

Answer 1

如果没有限制组中元素的最小数量或组具有相似数量的元素，则将除元素之外的所有元素k-1放在一个组中并且所有其他组由一个元素组成是最好的方法。要找到这些k-1创建k-1组的元素，请按降序排列成本并取第一个k-1出现的元素。