0

首先，我要声明我不要求任何代码或完整的解决方案。 我将描述问题：

您将获得一栋建筑物中的房间数量以及它们之间的走廊数量。每个走廊连接 2 个房间，并被赋予重量。总是可以到达任何房间。你应该通过移除它们来减少所有走廊的总重量，打印出减少的重量。

这些假设是否正确？：

  1. 建筑物是一个图形，房间是顶点，走廊是连接它们的边。因此这是一个无向连通图。

  2. 您可以通过获取图的最小生成树的权重，然后将完整权重减去 MST 的权重来解决这个问题 - 结果是可以删除的走廊权重的总和。

我已经为 MST 实现了 Prim 算法，结果对于示例案例和我在 Internet 上找到的任何其他 MST 案例都是正确的。但是，评分服务器仍然给我“错误答案”，没有其他信息。我不知道怎么了。输入中不超过 100 个顶点和 5000 条边，因此范围应该不是问题。权重是整数 <=200。我正在为 MTS 使用邻接矩阵。示例输入：

5 7  
1 2 50  
2 3 40  
3 4 20  
4 5 10  
1 4 40  
3 5 30

在这种情况下，程序打印 80。完整的重量是 190，最小重量是 110，所以我们可以删除 190 - 110 = 80

我的问题是：

  1. 有没有什么明显的错误浮现在你的脑海中？需要注意的事项，为什么它适用于示例输入等。
  2. 互联网上是否有任何中等规模的 MST 测试用例可用于查找问题？
  3. 有没有其他方法可以解决这个问题？我很乐意用评分服务器尝试任何事情。

我对图表完全陌生，所以我可能会遗漏一些东西。

4

1 回答 1

0
  1. 建筑物是一个图形，房间是顶点，走廊是连接它们的边。因此这是一个无向连通图。
  2. 您可以通过获取图的最小生成树的权重，然后将完整权重减去 MST 的权重来解决这个问题 - 结果是可以删除的走廊权重的总和。

是的，这两个都是正确的（以建筑不是一个以房间为顶点、走廊为边的图形的挑剔取模，但可以这样看待）。如果你这样看，原始图的总权重与最小生成树的总权重之间的差异是在不使某些房间无法与其他房间接触的情况下最大可能地减少权重（即使图断开连接）。

所以我看到了两种可能性，

  1. 您在 Prim 算法的实现中有一个细微的错误，该错误由评分服务器上的测试用例触发，而不是由您检查的测试用例触发。
  2. 评分服务器有错误的答案。

如果没有任何进一步的信息，我会认为 1 更有可能。

有没有其他方法可以解决这个问题？我很乐意用评分服务器尝试任何事情。

由于您需要找到 MST 的重量，因此我不知道您如何在不找到 MST 的情况下做到这一点。因此，其他方法是找到 MST 的不同算法。我想到了克鲁斯卡尔的算法。

于 2013-03-03T21:39:13.530 回答