插头dp的连通性测验

2017-10-01 12:15分类：电子技术阅读：

啥是插头dp

像这么在一个n*m的棋盘上（n与m很小），求有多少种纷歧样的回路数，或是用1条回路经过悉数点或有些点的计划数，或是求一条途径上的权值和最大的疑问。
通常称为插头dp。
这类疑问通常很显着，但代码量大又简略犯错，有时TLE有时MLE。
通常解法

插头：关于一个4连通的疑问来说，它通常有上下摆布4个插头，一个方向的插头存在标明这个格子在这个方向能够与外面相连。
关于一个回路上的格子，必定是从一个方向进入另一个方向出去，共有图示6中或许。
解插头dp的通常办法是逐格递推，依照从上到下，从左到右的次第顺次思考每一格

咱们称图中的蓝线为归纳线，任何时分只需归纳线上方的格子才会对归纳线以下的格子发作直接的影响。
以图中第三行第三列的格子D为例，假定逐格推到其时格子：
当左面有向右的插头，上边有向下的插头，那么D只能思考左上插头。
当左面有向右的插头、上边向下的插头中有且只需一个，那么D能够接遭到该方向的插头并有向右或向下两个插头的其间一个。
当左面上边都没有插头时，D能够有右下插头。
这三种状况便是在递推时要思考的底子状况。
易知，关于m列的格子，归纳线上有m+1个插头信息，m个格子的上方的插头信息，以及其时推到的格子左面的插头信息。

那么关于一条路的疑问，该怎样确保终究在图中只需一个连通重量呢。
咱们用最小标明法标明格子的连通性。
悉数的阻遏格子符号为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
咱们用两个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){
if (state==st){
f+=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
编码的进程并不杂乱，只需运用状况紧缩的常识依照必定的规矩将数组中的值贮存在一个整数的纷歧样位上即可。
因为标题中m
留神在压位的进程中，因为在兼并纷歧样连通性的插头时会消去一个连通重量，因而要对连通性的编号从头做处理，从头按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
解码愈加简略。
void decode(int code[],int m,LL st){
for (int i=m;i>=0;i--){
code=st&7;
st>>=3;
}
shift 函数将code中的悉数元素向右移动一位。当j==m时需求这么做。
void shift(int code[],int m){
for (int i=m;i>0;i--) code=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
一个阻遏是不或许有向下或向右的插头的，将其设为0。
void dpblock(int i,int j,int cur){
for (int k=0;k
这悉数进程正本便是一个插头dp的模板