首页 > 代码库 > 插头与轮廓线与基于连通性状态压缩的动态规划
插头与轮廓线与基于连通性状态压缩的动态规划
问题定义
什么是插头DP
在一个n*m的棋盘上（n与m很小），求：
- 有多少种不同的回路数
- 用1条回路经过所有点的方案数
- 用1条回路经过部分点的方案数
- 1条路径上的权值和最大
的这一类问题，通常可以用插头DP来解决。
这类问题通常很明显，但代码量大又容易出错，有时TLE有时MLE。
什么是基于状态压缩的动态规划
基于状态压缩的动态规划问题是一类以集合信息为状态且状态总数为指数级的特殊的动态规划问题。
在状态压缩的基础上，有一类问题的状态中必须要记录若干个元素的连通情况，我们称这样的问题为基于连通性状态压缩的动态规划问题。
什么是插头
对于一个4连通的问题来说，它通常有上下左右4个插头，一个方向的插头存在表示这个格子在这个方向可以与外面相连。
一个回路上的格子，必然是从一个方向进入另一个方向出去，共有图示6种可能。
什么是轮廓线
图中的蓝线称为轮廓线。
任何时候只有轮廓线上方的格子才会对轮廓线以下的格子产生直接的影响。
显然，对于m列的格子，轮廓线上有m+1个插头信息，包括m个格子的上方的插头信息，以及当前格子左侧的插头信息。
一般解法
在解题的过程中，把轮廓线作为动态规划的状态进行转移。逐格递推，按照从上到下，从左到右的顺序依次考虑每一格。
以上边轮廓线图中第三行第三列的格子D为例，假设现在已经逐格推到它：
由于上方格子存在插头IV，因此D必须有向上的插头。
若左侧格子存在插头III，那么D必须有向左的插头。（D只能为左上插头）
若左侧格子存在插头II，那么D不能有向左的插头。（D可以为上下插头或上右插头）
当左边有向右的插头、上边有向下的插头时（插头III、插头IV存在），D必须有左上插头。
在递推时，要根据左边上边的插头情况来递推右边下边的插头。
逐格递推示意图：
连通性
如果题目的要求是1条回路，我们得到的却有可能得到下图的情况。
该如何保证最后在图中只有一个连通分量呢。
我们用最小表示法表示格子的连通性。
所有的障碍格子标记为0，第一个非障碍格子以及与它连通的所有格子标记为1，然后再找第一个未标记的非障碍格子以及与它连通的格子标记为2，……，重复这个过程，直到所有的格子都标记完毕。
当两个属于不同连通分量的格子合并到一起时，我们将所有属于这两个连通分量的格子的连通性更新，使其具有相同的值。
算法描述
逐格递推，在每一行开始时，用一个数组表示轮廓线，数组中存放着m个元素，即m列，上一行的每一列是否有向下的插头。
在每个格子开始时，我们要知道这个格子左侧的是否有插头、上方是否有插头。
在每个格子结束时，我们要设置下一行同一列的格子的插头，也要设置当前格子右边的插头信息。
为了处理方便，我们要把递推到每个格子时的轮廓线用一个整数来表示，这个过程称为encode。
对于m列的格子，用一个m+1的数组code来表示轮廓线上的信息（包括连通性）。
对于当前的格子(i,j)，code[j-1]中是它左侧格子的插头信息，code[j]中时它上方格子的插头信息。
我们根据这两个值处理(i,j)的所有可能的状态，然后将 code[j-1]设为(i,j)下方格子的插头信息，code[j]设为(i,j)右侧插头信息。
将code数组编码为整数，作为(i,j+1)格子的起始状态。
当j已经是最后一列时，我们将code数组的所有元素向右平移，将第一个元素code[0]设为0。
这样对于一个新的一列，code数组就能表示它上方所有格子的信息。
对于涉及到连通性的问题，code数组储存的是插头的连通性。
对于不涉及连通性的问题，code数组储存插头的有无。
代码实现
【例】Formula 1 [Ural1519]
给你一个m * n的棋盘，有的格子是障碍，问共有多少条回路使得经过每个非障碍格子恰好一次．m, n ≤ 12．
首先将棋盘读入，有障碍的格子设为0，没有障碍设为1，注意要将棋盘之外的格子都设为有障碍。
题目要求要经过所有的格子，这说明在某个格子形成闭合回路时，在它之后不会再有别的空格子了，因此形成闭合回路的格子必定是最右下的格子，用(ex,ey)表示。
memset(maze,0,sizeof(maze)); ex=ey=0; for (int i=1;i<=n;i++){ scanf("%s",s+1); for (int j=1;j<=m;j++){ if (s[j]==‘.‘){ maze[i][j]=1; ex=i; ey=j; } } }
我们用两个hash表来储存当前格子轮廓线上所有可能的状态与下一个格子轮廓线所有可能的状态。
这种状态可能出现的次数记在 f 中。
struct HASHMAP{ int head[seed],next[maxn],size; LL state[maxn]; LL f[maxn]; void clear(){ size=0; memset(head,-1,sizeof(head)); } void insert(LL st,LL ans){ int h=st%seed; for (int i=head[h];i!=-1;i=next[i]){ if (state[i]==st){ f[i]+=ans; return; } } state[size]=st; f[size]=ans; next[size]=head[h]; head[h]=size++; } }hm[2];
主要处理过程如下，轮流使用两个哈希表存储状态。递推格子，如果当前无障碍，则调用 dpblank，否则调用 dpblock。
递推完最后一个格子后，将所有可能的状态中的方案数相加即为答案，实际上对于本题来说，最终只会有一个状态，就是code数组中的元素全为0，因为最后行上不可能有向下的插头。
int cur=0; LL ans=0; hm[cur].clear(); hm[cur].insert(0,1); for (int i=1;i<=n;i++){ for (int j=1;j<=m;j++){ hm[cur^1].clear(); if (maze[i][j]) dpblank(i,j,cur); else dpblock(i,j,cur); cur^=1; } } for (int i=0;i<hm[cur].size;i++){ ans+=hm[cur].f[i]; }
编码的过程并不复杂，只要利用状态压缩的知识按照一定的规则将数组中的值储存在一个整数的不同位上即可。
由于题目中m<=12，所以显然最多只有6个不同的连通分量。因此code数组中元素的值不应超过6，用3个二进制位来表示0~7的整数。
注意在压位的过程中，由于在合并不同连通性的插头时会消去一个连通分量，因此要对连通性的编号重新做处理，重新按1~cnt编码。
LL encode(int code[],int m){ LL st=0; int cnt=0; memset(ch,-1,sizeof(ch)); ch[0]=0; for (int i=0;i<=m;i++){ if (ch[code[i]]==-1) ch[code[i]]=++cnt; code[i]=ch[code[i]]; st<<=3; st|=code[i]; } return st; }
解码更加简单。
void decode(int code[],int m,LL st){ for (int i=m;i>=0;i--){ code[i]=st&7; st>>=3; }
shift 函数将code中的所有元素向右移动一位。当j==m时需要这样做。
void shift(int code[],int m){ for (int i=m;i>0;i--) code[i]=code[i-1]; code[0]=0; }
对空位置处理时，先枚举当前可能的所有的轮廓线状态。
对于每个状态，先用 decode 解码出 code 数组。
那么它左侧的信息left=code[j-1]，上方的信息up=code[j]。
按照一般解法中所说的情况进行讨论。
当左上有插头时，当两个插头属于相同的连通分量时，如果这个格子恰好是最后一个格子才能合并回路。两个插头不属于相同连通分量时，合并它们。
对于左边有一个插头或上方有一个插头的情况，判断右边或下边是否是障碍，如果不是的话就连接一个插头，这个插头跟接入这个格子的插头属于相同的连通分量。
对于没有插头的格子，那么他只能是一个新的连通分量，向右下设置插头。将新的连通分量设为一个不可能出现的最大值，当编码时会对它重新设置，不用担心溢出。
对于每一种讨论出的状态，将其加入下一个哈希表中。
当j==m时，在编码之前要进行shift，但是某些情况下j不可能等于m，因此不做shift操作也可以。
void dpblank(int i,int j,int cur){ int left,up; for (int k=0;k<hm[cur].size;k++){ decode(code,m,hm[cur].state[k]); left=code[j-1]; up=code[j]; if (left&&up){ if (left==up){ if (ex==i&&ey==j){ code[j-1]=code[j]=0; if (j==m) shift(code,m); hm[cur^1].insert(encode(code,m),hm[cur].f[k]); } } else{ code[j-1]=code[j]=0; for (int i=0;i<=m;i++){ if (code[i]==left) code[i]=up; } if (j==m) shift(code,m); hm[cur^1].insert(encode(code,m),hm[cur].f[k]); } } else if (left||up){ int t; if (left) t=left; else t=up; if (maze[i][j+1]){ code[j-1]=0; code[j]=t; hm[cur^1].insert(encode(code,m),hm[cur].f[k]); } if (maze[i+1][j]){ code[j-1]=t; code[j]=0; if (j==m) shift(code,m); hm[cur^1].insert(encode(code,m),hm[cur].f[k]); } } else{ if (maze[i][j+1]&&maze[i+1][j]){ code[j-1]=code[j]=13; hm[cur^1].insert(encode(code,m),hm[cur].f[k]); } } } }
一个障碍是不可能有向下或向右的插头的，将其设为0。
void dpblock(int i,int j,int cur){ for (int k=0;k<hm[cur].size;k++){ decode(code,m,hm[cur].state[k]); code[j-1]=code[j]=0; if (j==m) shift(code,m); hm[cur^1].insert(encode(code,m),hm[cur].f[k]); } }
这整个过程其实就是一个插头dp的模板（山寨自kuangbin大牛）。
经典问题
HDU 1693 Eat the Trees
多回路经过所有格子的方案数。
不需要记录连通性，最简单的题，对所有空格子都考虑适当的插头即可。
URAL 1519 Formula 1
单回路经过所有格子的方案数。
记录连通性的入门题，要保证只在最后一个格子形成回路。
FZU 1977 Pandora adventure
单回路数，格子有了三种：障碍格子、必选格子和可选格子。
在编码时添加一位标志，表示是否形成了回路，如果形成了回路后还遇到了必选格子，就废弃掉这个状态。
HDU 1964 Pipes
单回路求最小花费。
求花费的题，在哈希时改为记录当前的最佳值。在最后一个格子判断才能形成回路。
HDU 3377 Plan
从左上角走到右下角，可选格子，每个格子有个分数，求最大分数。
对左上和右下的格子单独进行处理，左上的格子只能有向下或向右的插头，而右下的格子只能有向上和向左的插头，不能形成回路。
POJ 1739 Tony‘s Tour
从左下角走到右下角，每个非障碍格子仅走一次的方法数。
在最后添加两行，倒数第二行中间部分全设置为障碍。然后求一条回路的方案数即可。
POJ 3133 Manhattan Wiring
格子中有两个2，两个3.求把两个2连起来，两个3连起来。 两条路径不能交叉。
对2和3的点单独进行考虑，格子上不能形成回路，而且只有出入两种可能，加上方向只有四种可能。
连通性只有两个选择2或3。对于不确定2还是3的普通格子就两个都尝试一下。
ZOJ 3466 The Hive II
多回路走有障碍的六边形格子，求方案数。
将格子行列颠倒一下，发现一个格子有6个方向的插头，左右，加上上边两个下边两个。
将code数组扩展成两倍，一个格子占用code数组中的三个元素，code[2*j-2]为左边的插头，code[2*j-1]为左上的插头，code[2*j]为右上的插头。
按照不同情况进行推导之后，将code[2*j-2]为左下的插头，code[2*j-1]为右下的插头，code[2*j]为右边的插头。这样下一个格子仍然可以从code中取到合适的信息。
而奇数行与偶数行的左下与右下坐标的计算方法是不同的，这个要注意处理，而且由于六边形的特殊性，只有偶数行才需要shift操作。
ZOJ 3213 Beautiful Meadow
简单路径得到最大的分数。
HDU 4285 circuits
求K个回路的方案数。不能环套环。
将当前的闭合回路数压入状态中。
对于环套环，如果当前格子左边有奇数个不同连通分量的插头，那么如果在左上形成闭合的回路，那么就会出现环套环的情况，只要对这种情况跳过即可。