状压DP初步之POJ 2288

发表于

Islands and Bridges

来源

Suppose there are n islands. The value of a Hamilton path C1C2…Cn is calculated as the sum of three parts. Let Vi be the value for the island Ci. As the first part, we sum over all the Vi values for each island in the path. For the second part, for each edge CiCi+1 in the path, we add the product ViVi+1. And for the third part, whenever three consecutive islands CiCi+1Ci+2 in the path forms a triangle in the map, i.e. there is a bridge between Ci and Ci+2, we add the product ViVi+1*Vi+2.

Most likely but not necessarily, the best triangular Hamilton path you are going to find contains many triangles. It is quite possible that there might be more than one best triangular Hamilton paths; your second task is to find the number of such paths.

以上是本题的描述，好像做了一篇英语阅读理解～～，为了更好解题，手动翻译：
假设有n个岛，一条汉密尔顿路C1C2…Cn 由三部分的和计算。让Vi成为岛Ci的价值。作为第一部分，我们将路径上所有Vi相加；作为第二部分，对于每一条边CiCi+1，我们增加ViV(i+1)；作为第三部分，当路径上的CiCi+1Ci+2形成了一个三角形，即Ci与Ci+2之间有较大距离时，我们增加ViV(i+1)V(i+2)
最有可能但不一定，你要找到的的最佳三角形哈密尔顿路包含许多三角形。你的第二个任务是找到这样的路径数量。
目的就是求最大价值并找到路径数量。

总权值包括三部分

第1部分，v[i]之和

第2部分，v[i]v[i+1]之和

第3部分，如果岛屿c[i]与岛屿c[i+2]也是相通的，即岛屿c[i]，c[i+1]，c[i+2]构成了一个三角关系，v[i][i+1]*[i+2]之和

哈密尔顿回路：在一个无向图中，由指定的起点前往指定的终点，途中经过所有其他节点且只经过一次

Input

The input file starts with a number q (q<=20) on the first line, which is the number of test cases. Each test case starts with a line with two integers n and m, which are the number of islands and the number of bridges in the map, respectively. The next line contains n positive integers, the i-th number being the Vi value of island i. Each value is no more than 100. The following m lines are in the form x y, which indicates there is a (two way) bridge between island x and island y. Islands are numbered from 1 to n. You may assume there will be no more than 13 islands.

Output

For each test case, output a line with two numbers, separated by a space. The first number is the maximum value of a best triangular Hamilton path; the second number should be the number of different best triangular Hamilton paths. If the test case does not contain a Hamilton path, the output must be `0 0’.

Note: A path may be written down in the reversed order. We still think it is the same path.

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2
3 3
2 2 2
1 2
2 3
3 1
4 6
1 2 3 4
1 2
1 3
1 4
2 3
2 4
3 4

Sample Output

1
2
3

22 3
69 1

思想

显然，这是一道使用动态规划求解的题（符合重叠子问题原则）
如果要用朴素的方法建立数组实现，显然空间会炸。因此，这里要使用状态压缩。
每个点的状态由前两个点所决定，我们用F(s,i,j)表示状态为s时，当前点为i,上一个点为j是的最大价值。这个状态由F(s’,j,k)推导。
如何表示状态呢？二进制的某一位代表了这个位上的点的情况。若为1，则走过，若为0，则没有走过。
因此，我们可以推导出s’=s-(1<<i)，回溯到了这一步之前一步的状态。
状态转移：F(s,i,j)=max{F(s,i,j),F[s’,j,k]+tmp} tmp指的是加上的得分，即ViVj+Vi,如果构成三角关系（i和k间有边）,tmp就要加上ViVjVk
边界：F((1<<i)+(1<<j),i,j)=Vi+Vj+ViVj(i与j要有边）

注意

  1. n=1时，路径的条数是1
  2. 技术要用_int64,因为有13个岛，即最多路径为2^13,超过int
  3. 最后输出路径的时候要除以2，因为题目说颠倒路径只算1条
  4. 如果哈密顿路不存在，输出“0 0”

    代码实现

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79

     #include <cstdio>
     #include <cstring>
     using namespace std;
     int v[15],g[15][15];
     long long f[1<<13][13][13],p[1<<13][13][13];
     int main(){
      int t;
      long long ans=0,sum=0,tmp=0,st=0;
      scanf("%d",&t);
      while(t--){
       ans=-1,sum=0;
       memset(v,0,sizeof(v));
       memset(g,0,sizeof(g));
       memset(f,-1,sizeof(f));
       memset(p,0,sizeof(p));
       int n,m;
       scanf("%d%d",&n,&m);
       for(int i=0;i<n;++i)scanf("%d",&v[i]);
       for(int i=0;i<m;++i){
        int x,y;
        scanf("%d%d",&x,&y);
        --x,--y;
        g[x][y]=g[y][x]=1;
       }
       if(n==1){//特殊情况 
        printf("%d 1\n",v[0]);
        continue;
       }
       for(int i=0;i<n;++i){//预处理 
        for(int j=0;j<n;++j){
    	    if(i!=j&&g[i][j]){
    		    f[(1<<i)+(1<<j)][i][j]=v[i]+v[j]+v[i]*v[j];
    		    p[(1<<i)+(1<<j)][i][j]=1;
    	    }
        }
       }
       for(long long s=0;s<(1<<n);++s){//生成情况 
        for(int i=0;i<n;++i){
    	    if(s&(1<<i))
    	    for(int j=0;j<n;++j){
    		    if(i!=j&&g[i][j]&&s&(1<<j))
    		    for(int k=0;k<n;++k){
    			    if(i!=k&&j!=k&&s&(1<<k)&&g[j][k]){
    				    st=s-(1<<i);
    				    if(f[st][j][k]!=-1){//已经符合初始化的条件，即三步价值的第一步 
    					    tmp=v[i]+v[i]*v[j]+f[st][j][k];
    					    if(g[k][i])//成环情况
    					    tmp+=v[i]*v[j]*v[k];
    					    if(tmp>f[s][i][j]){//更新 
    						    f[s][i][j]=tmp;
    						    p[s][i][j]=p[st][j][k];//转移路径 
    					    } 
    					    else if(tmp==f[s][i][j])p[s][i][j]+=p[st][j][k];//对路径叠加 
    				    }
    			    }
    		    }
    	    }
        }
       }
       for(int i=0;i<n;++i){
        for(int j=0;j<n;++j){
    	    if(i!=j){
    		    if(f[(1<<n)-1][i][j]>ans){//(1<<n -1即全部走过的值
    		        ans=f[(1<<n)-1][i][j];
    		        sum=p[(1<<n)-1][i][j];
    		    }
    		    else if(f[(1<<n)-1][i][j]==ans)
    		    sum+=p[(1<<n)-1][i][j];
    	    }
        }
       }
       if(ans==-1)//无效情况
       printf("0 0\n");
       else
       printf("%lld %lld\n",ans,sum/2); 
      }
      return 0;
    }

总结

  1. 不理解题意是无法正确解题的核心原因。看不懂一个题往往比不会做更可怕
  2. 状压DP不错，但要酌情考虑，容易炸空间～～～
  3. 熟悉位运算可以带来很大便利
    The End
    本文系原创，未经作者许可禁止转载。