Hamilton路径

一个状压dp模板题。
那么问题来了,为什么要进行状态压缩呢?
其实道理很简单,如果不进行压缩的话,dp数组需要写成dp2...2
最高需要MAXN+1维,这显然是我们所不能够接受的。
但是我们观察,每一维其实也就两个状态,即取与不取,这与我们的二进制开关性很像。
于是我们将20维状态压缩到一个20位的二进制数,即每一位代表状态取与不取。
dp方程为$$dp[i][j] = min(dp[i][j],dp[i去除j][k] + G[j][k]);$$
dp数组即在j点经过i里面保存的点的状态
下面给出参考代码:

#include <bits/stdc++.h>
#define f(a,b,c) for(int a=b;a<c;++a)
#define MAXN 20
using namespace std;

int n,ans;
int G[MAXN][MAXN];
int dp[1 << MAXN][MAXN];

int main() {
    ios::sync_with_stdio(false);

    cin >> n;

    f(i,0,n)
        f(j,0,n) 
            cin >> G[i][j];

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

    dp[1][0] = 0;
    for(int i = 1; i <= (1 << n) - 1; ++i)
        f(j,0,n)
            if((i >> j) & 1)
                f(k,0,n)
                    dp[i][j] = min(dp[i][j],dp[i ^ (1 << j)][k] + G[j][k]);

    cout << dp[(1 << n) - 1][n - 1] << endl;

    return 0;
}

对几个小细节进行解释:

  • 首先dp数组需要初始化成最大值
  • 在进行状态转移之前需要判断第j位是否已经被选择,即((i >> j) & 1)是否为真
  • (i ^ (1 << j))即取上一层状态(将第j位异或成0)
Last modification:July 30th, 2019 at 09:40 am
博客维护不易,如果你觉得我的文章有用,请随意赞赏

Leave a Comment