HDU 5402 模拟构造 Travelling Salesman Problem

题意：

有一个n * m的数字矩阵，每个格子放着一个非负整数，从左上角走到右下角，每个格子最多走一次，问所经过的格子的最大权值之和是多少，并且输出一个路径。

分析：

如果n和m有一个是偶数的话，那么只要按照蛇形的走法一直走下去即可。

比如n为奇数的时候就这样，左右左右地蛇形走。

同样的，如果m为奇数的时候，也可以上下上下地蛇形走。

但如果n和m都为偶数的时候，就会无法走完全部的格子，最终到达右下角。

但是可以少走一个格子，而且这个格子必须是那种行标加列标为奇数的格子才行(行和列从1开始)，所以我们就绕过权值最小的符合条件的格子，走其他所有的格子获得最大值。

比如像这种：

除了那个选出来的格子不走，其余的格子可以全部走到。

所以就直接这样构造出一条路径出来。

我们可以这样构造，假设选出来的不走的格子为(x, y)，把这个地图分成三部分：选第x行和相邻的一行，这两个作为一个「长城」的走法。

然后「长城」上面和下面用蛇字形走法，最后走到右下角。

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 using namespace std;

 const int maxn =  + ;

 int n, m, sum, _min;

 int a[maxn][maxn];

 int r, c;

 bool vis[maxn][maxn];

 void snake(int n, int m, char d, char revd, char nxt)

 {

     for(int i = ; i <= n; i++)

     {

         if(i & )

         {

             for(int j = ; j < m; j++) printf("%c", d);

             if(i < n) printf("%c", nxt);

         }

         else

         {

             for(int j = ; j < m; j++) printf("%c", revd);

             if(i < n) printf("%c", nxt);

         }

     }

 }

 int main()

 {

     while(scanf("%d%d", &n, &m) ==  && n)

     {

         sum = ;

         _min = ;

         for(int i = ; i <= n; i++)

             for(int j = ; j <= m; j++)

             {

                 scanf("%d", &a[i][j]);

                 sum += a[i][j];

                 if(((i + j) & ) && a[i][j] < _min) { _min = a[i][j]; r = i; c = j; }

             }

         if(n & )

         {

             printf("%d\n", sum);

             snake(n, m, 'R', 'L', 'D');

             puts("");

             continue;

         }

         if(m & )

         {

             printf("%d\n", sum);

             snake(m, n, 'D', 'U', 'R');

             puts("");

             continue;

         }

         printf("%d\n", sum - _min);

         if(r -  > ) snake(r - , m, 'R', 'L', 'D');

         if(r -  > ) printf("D");

         int x, y, up, down;

         if(r <= )

         {

             x = y = ;

             up = , down = ;

         }

         else

         {

             up = r - , down = r;

             x = r - ;

             if(r & ) y = m; else y = ;

         }

         memset(vis, false, sizeof(vis));

         for(int i = ; i <= n + ; i++) vis[i][] = vis[i][m + ] = true;

         for(int i = ; i <= m + ; i++) vis[][i] = vis[n + ][i] = true;

         vis[x][y] = true;

         vis[r][c] = true;

         if(y == )

         {

             for(int i = ; i <= m *  - ; i++)

             {

                 if(x == down)

                 {

                     if(!vis[x-][y]) { x--; vis[x][y] = true; printf("U"); }

                     else { y++; vis[x][y] = true; printf("R"); }

                 }

                 else

                 {

                     if(!vis[x+][y]) { x++; vis[x][y] = true; printf("D"); }

                     else { y++; vis[x][y] = true; printf("R"); }

                 }

             }

         }

         else

         {

             for(int i = ; i <= m *  - ; i++)

             {

                 if(x == down)

                 {

                     if(!vis[x-][y]) { x--; vis[x][y] = true; printf("U"); }

                     else { y--; vis[x][y] = true; printf("L"); }

                 }

                 else

                 {

                     if(!vis[x+][y]) { x++; vis[x][y] = true; printf("D"); }

                     else { y--; vis[x][y] = true; printf("L"); }

                 }

             }

         }

         if(down +  <= n)

         {

             printf("D");

             if(y == ) snake(n - down, m, 'R', 'L', 'D');

             else snake(n - down, m, 'L', 'R', 'D');

         }

         puts("");

     }

     return ;

 }

代码君

巴特西

HDU 5402 模拟构造 Travelling Salesman Problem

最新文章

热门文章

巴特西

HDU 5402 模拟 构造 Travelling Salesman Problem

最新文章

热门文章

HDU 5402 模拟构造 Travelling Salesman Problem