POJ1450：Gridland 【杂题】

题目大意：先给出了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;

}

巴特西

POJ1450：Gridland 【杂题】

最新文章

热门文章