【知识】 状态压缩动态规划 & 【题解】 P10447 最短 Hamilton 路径

前言

–>题目传送门<–

在洛谷题解提交晚了一步，没通过。

思路

题意简述：题面已经够简了。

算法：状态压缩动态规划模板。

啥是状态压缩？我不会！

慢慢听我讲嘛。

状态压缩：将复杂状态压缩为整数来达到优化转移的目的。

对于这道题，每个点只有走过和没走过两种情况，所以我们用二进制数就能解决。

对于一个二进制数，如果从左往右第 位是 ，就说明 点走过了，是 就说明还没走过。

比如对于二进制数 ，我们先列个表：

二进制数
对应位数

例如：

• 从右往左第 位上是 ，就说明 号点走过了。

• 从右往左第 位上是 ，就说明 号点还没走过。

• 以此类推……

那如何进行二进制数的操作呢？

首先你得知道位运算 。

1. 判断集合 中是否含有 点：

   if((S>>i)&1)

2. 求集合 去除 点后的集合：

   S^(1<<j)

3. 枚举集合 中的所有点：

   for(int i=0;i<=n;i++)
        if((S>>k)&1)
          ……

原理不难理解，请读者自行推导。

状态转移

这个和最短路的思路有点像。对于 状态下起点到 的“最短路径”，我们可以这样求：

枚举状态 （就是 状态中不走 时的情况）中的点 为中转点，然后把起点到 的“最短路径”加上 到 的距离，取个最小值就是答案了。

状态转移方程：。

那么我们最终的答案就是 。

代码实现

#include <bits/stdc++.h>
using namespace std;
int n,f[1<<20][21];
int dis[21][21];
int main(){
    memset(f,0x3f,sizeof(f));	//初始化最大值。
    cin>>n;
    for(int i=0;i<n;i++)	//输入图。
      for(int j=0;j<n;j++)
        cin>>dis[i][j];	        //输入各点间的距离。
    f[1][0]=0;			//初始值：集合中只有点 0，起点和终点都是 0。
    for(int S=1;S<(1<<n);S++)	//从小集合扩展到大集合，集合压缩为二进制数 S。
        for(int i=0;i<n;i++)	//枚举点 j。
            if((S>>i)&1)	//判断点 i 是否在 S 中。
                for(int k=0;k<n;k++)
                    if(((S^(1<<i))>>k)&1)	//判断 k 是否属于集合 S-i。
                        f[S][i]=min(f[S][i],f[S^(1<<i)][k]+dis[k][i]);
    cout<<f[(1<<n)-1][n-1];	//输出：路径包含了所有点，终点是 n-1。
    return 0;
}

其他

状态压缩不仅可以压缩成二进制，如果题目中一个元素（点）可以有 种甚至更多种的状态，我们就可以压缩成三进制或更高进制。