首页 > 代码库 > 【HDU 5402】Travelling Salesman Problem(构造)

【HDU 5402】Travelling Salesman Problem(构造)

被某题卡SB了,结果这题也没读好。。。以为每一个格子能够有负数就当搜索做了。怎么想也搜只是去,后来发现每一个格子是非负数,那么肯定就是构造题。


题解例如以下:

首先假设nn为奇数或者mm为奇数,那么显然能够遍历整个棋盘。

如果n,mn,m都为偶数,那么讲棋盘黑白染色,如果(1,1)(1,1)(n,m)(n,m)都为黑色,那么这条路径中黑格个数比白格个数多11,而棋盘中黑白格子个数同样,所以必定有一个白格不会被经过,所以选择白格中权值最小的不经过。

构造方法是这样,首先RRRRDLLLLD这种路径走到这个格子所在行或者上一行。然后DRUR这样走到这个格子的所在列或者前一列。然后绕过这个格子。

然后走完这两行,接着按LLLLDRRRR这种路径往下走。


这题须要说明一下为什么这么选,由于假设你选的不是 (i,j)互为奇偶的格子的话,肯定有其余的(i,j)互为奇偶的格子不能被走到。假设选择的话,仅仅有这一个格子不会被走到,所以依据贪心肯定要选这个格子了.


恩。。挺脑洞的一题。写起来倒是不难。


#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 105;
const int  INF = (1 << 30);
int mat[maxn][maxn];
int n,m,sum,minv,posx,posy;
void special_solve(){
    printf("%d\n",sum - minv);
    if(!(posx & 1)){
        for(int i = 0; i < posx; i++){
            char c = i & 1 ?

‘L‘ : ‘R‘; for(int j = 1; j < m; j++) printf("%c",c); printf("D"); } int base = 0; for(int i = 0; i < m; i++){ char c = (i + base) & 1 ? ‘U‘ : ‘D‘; if(i != posy) printf("%c",c); else base ++; if(i < m - 1) printf("R"); } for(int i = posx + 2; i < n; i++){ printf("D"); char c = i & 1 ? ‘R‘ : ‘L‘; for(int j = 1; j < m; j++) printf("%c",c); } } else{ for(int i = 0; i < posx - 1; i++){ char c = i & 1 ? ‘L‘ : ‘R‘; for(int j = 1; j < m; j++) printf("%c",c); printf("D"); } int base = 0; for(int i = 0; i < m; i++){ char c = (i + base) & 1 ?

‘U‘ : ‘D‘; if(i != posy) printf("%c",c); else base ++; if(i < m - 1) printf("R"); } for(int i = posx + 1; i < n; i++){ printf("D"); char c = i & 1 ? ‘R‘ : ‘L‘; for(int j = 1; j < m; j++) printf("%c",c); } } } int main(){ while(scanf("%d%d",&n,&m) != EOF){ sum = 0; minv = INF; for(int i = 0; i < n; i++) for(int j = 0; j < m; j++){ scanf("%d",&mat[i][j]); sum += mat[i][j]; if((i + j) & 1){ if(minv > mat[i][j]){ posx = i; posy = j; minv = mat[i][j]; } } } if(n & 1){ printf("%d\n",sum); for(int i = 0; i < n; i++){ char c = i & 1 ? ‘L‘ : ‘R‘; for(int j = 1; j < m; j++) printf("%c",c); if(i != n - 1) printf("D"); } } else if(m & 1){ printf("%d\n",sum); for(int i = 0; i < m; i++){ char c = i & 1 ? ‘U‘ : ‘D‘; for(int j = 1; j < n; j++) printf("%c",c); if(i != m - 1) printf("R"); } } else special_solve(); puts(""); } return 0; }



【HDU 5402】Travelling Salesman Problem(构造)