2012-0041

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

这是一个旅行商变种问题。本题目保证测试的样例一定小于等于OPT或者大于2OPT。其中OPT是理论最优解。所以你只需要找到一个回路，使得这条回路的长度小于等于2OPT，当然最优解是OPT所有找到的这条回路的长度一定大于等于OPT。也就是想办法先把所有的点连起来，且连接所有点的边之和小于OPT，这样，我们就可以double所有的边，这样可以选取其中若干边并添加另外一些边构造出回路。满足上面条件的一种构造方法就是最小生成树。假设我们最后构造出来的回路长度为A，则又因为这是欧氏空间，满足三角不等式，所以有OPT<=A<=2MST<=2OPT。得到这个不等式之后，就可以发现，只要求出MST，然后加倍之后。把测试用例和刚才得到的这个值相比就行了。

这是一个旅行商变种问题。本题目保证测试的样例一定小于等于OPT或者大于2OPT。其中OPT是理论最优解。所以你只需要找到一个回路，使得这条回路的长度小于等于2OPT，当然最优解是OPT所有找到的这条回路的长度一定大于等于OPT。也就是想办法先把所有的点连起来，且连接所有点的边之和小于OPT，这样，我们就可以double所有的边，这样可以选取其中若干边并添加另外一些边构造出回路。满足上面条件的一种构造方法就是最小生成树。假设我们最后构造出来的回路长度为A，则又因为这是欧氏空间，满足三角不等式，所以有OPT<=A<=2MST<=2OPT。得到这个不等式之后，就可以发现，只要求出MST，然后加倍之后。把测试用例和刚才得到的这个值相比就行了。