题目大意：先给出了TSP的背景，然后给出一个n*m的单位格点的图，图中除边缘上的点与八个方向的点有边连接，距离为欧拉距离，求从左上角出发的TSP
思路：从水题列表中看到的题，但看一开始给出的background是TSP就惊呆了，但看到题目觉得很好想。显然，行和列是对等的，并且当行列中有一个是偶数时都能像下图这样M状的遍历所有的点，通过割补发现线的长度为m*n。当m，n都为奇数时显然不能像上图那样遍历，因为是奇数，穿到下面后就没有点使它再回到上面了，但是发现增加一条斜边（长度为根号2）可以将问题转化为一边是奇数，一边是偶数的情况，此时长度为m*n-1+1.41=m*n+0.41 于是问题顺利解决
#include<cstdio>
#include<string.h>
#include<iostream>
using namespace std;
int main()
{
int t,m,n;
scanf("%d",&t);
for(int k=1;k<=t;k++)
{
scanf("%d%d",&m,&n);
if((m & 1) ==0 || (n & 1)==0){printf("Scenario#%d:\n%d",k,m*n);printf(".00\n\n");}
else {printf("Scenario#%d:\n%d",k,m*n);printf(".41\n\n");}
}
return 0;
}
原文：http://www.cnblogs.com/philippica/p/4006978.html