CH0103最短Hamilton路径 & poj2288 Islands and Brigdes【状压DP】

虐狗宝典学习笔记：

取出整数\(n\)在二进制表示下的第\(k\)位 \((n >> k) & 1)\)

取出整数\(n\)在二进制表示下的第\(0 ~ k - 1\)位（后\(k\)位） \(n & ((1 << k) - 1)\)

把整数\(n\)在二进制表示下的第\(k\)位取反 \(n xor (1 << k)\)

对整数\(n\)在二进制表示下的第\(k\)为赋值\(1\) \(n | (1 << k)\)

对整数\(n\)在二进制表示下的第\(k\)位赋值\(0\) \(n & (~(1 << k))\)

CH0103---最短Hamilton路径

http://contest-hunter.org:83/contest/0x00%E3%80%8C%E5%9F%BA%E6%9C%AC%E7%AE%97%E6%B3%95%E3%80%8D%E4%BE%8B%E9%A2%98/0103%20%E6%9C%80%E7%9F%ADHamilton%E8%B7%AF%E5%BE%84

题意：

hamilton指的是每个节点经过一次且仅经过一次的路径。现在路径上有权值，问最短的路径长度。

思路：

状压dp。\(dp[i][j]\)表示在状态是\(i\)且最后一个经过的点时\(j\)时的最短路径长度。

\(dp[i][j] = min{dp[i xor (i << j)][k] + weight(k, j)}\)

 #include <bits/stdc++.h>

 #define inf 0x3f3f3f3f

 using namespace std;

 typedef long long LL;

 int n;

 int g[][];

 int dp[ << ][];

 int main()

 {

     scanf("%d", &n);

     memset(dp, 0x3f, sizeof(dp));

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

         for(int j = ; j < n; j++){

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

         }

     }

     dp[][] = ;

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

         for(int j = ; j < n; j++){

             if(i >> j & ){

                 for(int k = ; k  < n; k++){

                     if((i ^  << j) >> k & ){

                         dp[i][j] = min(dp[i][j], dp[i ^  << j][k] + g[k][j]);

                     }

                 }

             }

         }

     }

     printf("%d\n", dp[( << n) - ][n - ]);

     return ;

 }

poj2288---Islands and Bridges

http://poj.org/problem?id=2288

题意：

有n个岛，m座桥。每座岛有一个val，一条汉密尔顿路径的值是路径中所有点的val之和，加上所有路径上相邻的两个岛的val乘积之和，加上路径上相邻的三个岛的val乘积之和。求最大的值以及方案数。

思路：

和CH0103很相近，不同的是这道题要多存一个岛。\(dp[stat][i][j]\)表示当前状态是\(stat\)，最后一个走的岛是\(j\),倒数第二个走的岛是\(i\), \(num\)数组表示对应的方案数。

当\( (stat, i, j) \)可达时，我们检查下一个要走的岛\(k\)，如果此时\( (stat >> k) & 1 == 0 \) 且 \( g[j][k] == 1 \)说明\(k\)是满足条件的

设\(tmp\)是下一个走\(k\)时的总价值。那么，\(dp[stat | (1 << k)][j][k] = max(dp[stat | (1 << k)][j][k], tmp)\)

如果\(tmp == dp[stat | (1 << k)][j][k]\),那么，\(num[stat | (1 << k)][j][k] += num[stat][i][j]\)。否则\(num[stat | (1 << k)][j][k] = num[stat][i][j] \)

那么要如何求\(tmp\) 呢。

首先当\(j\)可以走到\(k\)时，肯定有 \(tmp = dp[stat][i][j] + val[k] + val[j] * val[k] \)

如果此时还有\(g[i][k] == 1\) 那么\(tmp += val[i] * val[j] * val[k]\)

最后我们对于\(stat = (1 << n) - 1\)枚举\(i\)和\(j\)，找到最大的结果。

注意方案数会超出int。还需要注意\(n = 1\)时的特殊情况。

注意内存省着点，会MLE

 //#include <bits/stdc++.h>

 #include <iostream>

 #include <algorithm>

 #include <cmath>

 #include <cstring>

 #include <stdio.h>

 #include <vector>

 #include <map>

 #include <set>

 #define inf 0x3f3f3f3f

 using namespace std;

 typedef long long LL;

 int n, m, q;

 bool g[][];

 int dp[ << ][][];

 LL num[ << ][][];

 int val[];

 int cnt;

 void hamilton()

 {

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

     memset(num, , sizeof(num));

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

         for(int j = ; j < n; j++){

             if(g[i][j]){

                 dp[ << i |  << j][i][j] = val[i] + val[j] + val[i] * val[j];

                 num[ << i |  << j][i][j] = ;

             }

         }

     }

     for(int stat = ; stat <  << n; stat++){

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

             if((stat >> i) & ){

                 for(int j = ; j < n; j++){

                     if((stat >> j) & ){

                         if(g[i][j] && dp[stat][i][j] != -){

                             for(int k = ; k < n; k++){

                                 if(g[j][k] && k != i && ((stat >> k) & ) == ){

                                     int tmp = dp[stat][i][j] + val[k] + val[k] * val[j];

                                     if(g[i][k]){

                                         tmp += val[i] * val[j] * val[k];

                                     }

                                     if(tmp > dp[stat | ( << k)][j][k]){

                                         dp[stat | ( << k)][j][k] = tmp;

                                         num[stat | ( << k)][j][k] = num[stat][i][j];

                                     }

                                     else if(tmp == dp[stat | ( << k)][j][k]){

                                         num[stat | ( << k)][j][k] += num[stat][i][j];

                                     }

                                 }

                             }

                         }

                     }

                 }

             }

         }

     }

     //return dp[(1 << n) - 1][n - 1];

 }

 int main()

 {

     scanf("%d", &q);

     while(q--){

         memset(g, , sizeof(g));

         scanf("%d%d", &n, &m);

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

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

         }

         for(int i = ; i < m; i++){

             int u, v;

             scanf("%d%d", &u, &v);

             g[u - ][v - ] = ;

             g[v - ][u - ] = ;

         }

         if(n == ){

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

             continue;

         }

         hamilton();

         int maxi = ;

         LL ans = ;

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

             for(int j = ; j < n; j++){

                 if(g[i][j]){

                     if(maxi < dp[( << n) - ][i][j]){

                         maxi = dp[( << n) - ][i][j];

                         ans = num[( << n) - ][i][j];

                     }

                     else if(maxi == dp[( << n) - ][i][j]){

                         ans += num[( << n) - ][i][j];

                     }

                 }

             }

         }

         printf("%d %lld\n", maxi, ans / );

     }

     return ;

 }

巴特西

CH0103最短Hamilton路径 & poj2288 Islands and Brigdes【状压DP】

最新文章

热门文章