DP:Islands and Bridges(POJ 2288)

　　　　　　　　　　　　　　　　2015-09-21

　　　　　　　　　　　　　　　　造桥基建工程

　　题目大意，就是有n座岛和k座桥，要你找一条哈密顿圈（找完所有的岛，并且每个岛只经过一次），当经过一座岛就加上岛的价值，如果两岛联通，则加上两座岛的价值之积，如果三座岛之间构成三角联通，则再加上三岛之积，问最大价值的哈密顿圈和最大价值和哈密顿圈的个数

　　哈密顿圈是是一个NP完全的问题，用DP就可以解决这个问题，现在的问题就是，怎么解决呢？

　　首先我们要明确，这一题要用DP做什么，首先这一题的最后肯定要求到最后岛全部都通过的情况，然后还需要保留前两个岛的信息

　　那么这个时候我们可以想到用状态压缩去做（因为这里岛只能经过一次，而且经过以后状态都是等效的）101111，就表示第五个岛还没被经过，本来呢这个状态压缩应该是保留状态的，但是这样一来我们就需要保留1<<n个*3个维度，那么这一题我们可以放弃了，因为内存肯定不够，所以我们要想着优化储存空间，由于我们只用担心前两个岛是什么，而不是岛的所在状态（反正表示也是1001111）这样的，所以我们可以把两个岛的维度改为n*n，那么最后dp就是一个[1<<n][n][n]的三维数组

　　具体而言，对于不合法的位置，我们老方法，要定义其为-1，同时还要判断图是否联通

　　我们先从i=1（0000....0001）开始枚举，表示岛已经经过的位置，如果我们需要上一次还没来到这个岛的位置的状态，我们使用i^(1<<(j-1))这个方法，并且判断第j个岛的前两座岛是否有冲突。

　　如果算出来的dp值比dp[i][j][k]要大，则更新，并且num是继承dp[state_old][k][q]的状态，如果想等，则使num[i][j][k]+=num[state_old][k][q]（表示还有更多的路与此状态相关）。

　　最后基准状态，q=0的时候可以放入岛的价值，那么最后就可以一起处理了，并且只有一个岛的时候，要单独处理，并且数据类型要是long long

　　参考：http://blog.csdn.net/lenleaves/article/details/7981788

 #include <stdio.h>

 #include <stdlib.h>

 #include <string.h>

 static int islands_value[];

 int map[][];

 long long dp[ << ][][];//因为要保存两个以上状态，所以必须是三维数组，前面一位是状态数

 long long num[ << ][][];

 void Search(const int);

 static int If_Valid(const int, const int);

 int main(void)

 {

     int sum_islands, sum_paths, sum_obj, i, j, k, x, y;

     scanf("%d", &sum_obj);

     for (i = ; i < sum_obj; i++)//输入

     {

         scanf("%d%d", &sum_islands, &sum_paths);

         for (j = ; j <= sum_islands; j++)

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

         memset(map, , sizeof(map));

         memset(dp, -, sizeof(dp));

         memset(num, , sizeof(num));

         for (k = ; k < sum_paths; k++)

         {

             scanf("%d%d", &x, &y);

             map[x][y] = map[y][x] = ;//读图1

         }

         Search(sum_islands);

     }

     return ;

 }

 static int If_Valid(const int x, const int y)

 {

     /*If_Value函数：

      功能：判断y位置是否被访问过

      返回值：被访问过返回1，未被访问放回0,如果y是0，则就是基准情况，一定要给通过

     */

     if (y == ) return ;

     if (x&( << (y - ))) return ;

     else return ;

 }

 void Search(const int sum_islands)

 {

     int i, j, k, q, state_old;

     long long tmp, ans1, ans2;

     if (sum_islands == )

     {

         printf("%d 1\n", islands_value[]);

         return;

     }

     for (j = ; j <= sum_islands; j++)

     {

         dp[ << (j - )][j][] = islands_value[j];

         num[ << (j - )][j][] = ;//初始化的时候价值为1

     }

     for (i = ; i < ( << sum_islands);i++)

     {

         for (j = ; j <= sum_islands; j++)

         {

             state_old = i ^ ( << (j - ));//得到当j还没有出现时候的位置

             if (If_Valid(i, j))//这个位置就是要考虑的位置

             {

                 for (k = ; k <= sum_islands; k++)

                 {

                     if (k != j && map[j][k] && If_Valid(i, k))

                     {

                         for (q = ; q <= sum_islands; q++)

                         {

                             if (!map[k][q] && q) continue;//q = 0的时候是没有意义的

                             if (q != j&&q != k

                                 && If_Valid(state_old, q)//是否是需要的q

                                 && dp[state_old][k][q] != -)//这个位置一定要有意义

                             {

                                 tmp = islands_value[j] + islands_value[j] * islands_value[k] + dp[state_old][k][q];

                                 if (map[j][q])

                                     //假设j和q是联通的

                                     tmp += islands_value[j] * islands_value[k] * islands_value[q];

                                 if (tmp == dp[i][j][k])

                                     //如果得到的结果是和ijk这个位置已经重复了，则自增(中间状态)

                                     num[i][j][k] += num[state_old][k][q];

                                 if (tmp > dp[i][j][k])

                                     //如果比ijk这个状态还要大，则更新dp，继承num

                                 {

                                     dp[i][j][k] = tmp;

                                     num[i][j][k] = num[state_old][k][q];

                                 }

                             }

                         }

                     }

                 }

             }

         }

     }

     for (ans1 = -, ans2 = , j = ; j <= sum_islands; j++)

     {

         for (k = ; k <= sum_islands; k++)

         {

             if (k != j)

             {

                 if (ans1 == dp[( << sum_islands) - ][j][k])

                     ans2 += num[( << sum_islands) - ][j][k];

                 if (ans1 < dp[( << sum_islands) - ][j][k])

                 {

                     ans1 = dp[( << sum_islands) - ][j][k];

                     ans2 = num[( << sum_islands) - ][j][k];

                 }

             }

         }

     }

     if (ans1 == -)

         printf("0 0\n");

     else

         printf("%lld %lld\n", ans1, ans2 / );

 }

巴特西

DP:Islands and Bridges(POJ 2288)

最新文章

热门文章