毒瘤动规-----插头dp
y2823774827y
2018-12-17 19:24:09
## 近期图床经常崩掉，如其中图片无法显示，请移步博客园$\Longrightarrow$[更好的食用](https://www.cnblogs.com/y2823774827y/p/10140757.html)
## **插头dp**:
$A:$插头dp是什么？
$B:$一种基于连通性状态压缩的动态规划问题
$A:$请问有什么应用呢？
$B:$各种网格覆盖问题，范围允许状压解决，常用于计算方案数与联通块权值
$A:$轮廓线与插头呢？？？
$B:$轮廓线是状压的部分，用于解决插头的情况，不同于常见的状压dp，为了更好地处理状态，通常要要到括号表示法、最小表示法等，插头是格与格中的转移，可理解成将拼图连接的位置
$A:$本文将讲解哪些类型的题目呢？
$B:$单回路覆盖方案数，多回路覆盖方案数，骨牌覆盖，联通块最大权，单回路最大权，最小联通块方案，特殊型覆盖，多种限制的最大权
$A:$那我们开始吧！！
**各种例题：**
ps：以下的图都并非唯一状态，基于让读者更好理解采用最经典的图例
## 模板： [P5056 【模板】插头dp](https://www.luogu.org/problemnew/show/P5056)
题目大意
>给出n*m的方格，有些格子不能铺线，其它格子必须铺，形成一个闭合回路。问有多少种铺法？n,m(2<=n,m<=12)
状态：
此题面对一种状态，只考虑格子上方（我们叫它下插头）和左方（我们叫它右插头）插头情况，因为暂时只被这两个插头所影响，通过对插头不同情况的处理完成状态转移
此格与下一格的轮廓线如下图
 
状态转移实际如下
$b1$ 、$b2$分别表示右插头和下插头
我们知道一条线，是有左端点和右端点的，$0$表示无插头，$1$表示左端点，$2$表示右端点
来看这副图，在$(3,4)$轮廓线上有四个插头，**括号表示法**状态：(##)(##)，四进制表示此状态：$10021002$，明明只出现$0$ $1$ $2$，为什么不用三进制？因为位移更方便
以前的状压不是通常有就为$1$无就为$0$吗？
那我们为什么这里要用括号匹配四进制，因为$b1==2$ $and$ $b2==1$和$b1==1$ $and$ $b2==2$的状态产生的结果截然不同，不懂没关系，慢慢来，后文自有介绍
**当前点不能走(障碍)**
$(1)$ 则$!b1$ $and$ $!b2$才能产生状态转移，有插头就代表会走到该点，
不能走当然得两边都没有插头，，转移后当然这两小段插头也为空，直接添加状态就好了，这里就不放图了，脑补$qwq$
**当前点能走(非障碍必须走)**
$(1)$ $!b1$ $and$ $!b2$，则要加两个插头(一个左插头，一个有插头)，确保该点走过
$(2)$ $!b1$ $and$ $b2$只有一个插头，该插头向下延伸，选择直走或往右拐，等同于延续一个连通分量
此时插头的括号状态不变，通俗地说，就是插头本来是几转移后也是几
注意，插头在轮廓线上的位置变了，如果直走$b2$的位置为$0$，$b1$为原来的$b2$
 
$(3)$ $b1$ $and$ $!b2$则向右延伸，直走或向下拐，与$(2)$同理
 
$(4)$ $b1==1$ $and$ $b2==1$ 两个插头相遇，等同于合并两个连通分量，下一次$b1$和$b2$的位置就为$0$了
但这里合并后并非直接删去插头即可，因为这样就只剩下两个右插头了，起不了匹配的效果
得$O(m)$往右扫找另一边匹配的右括号，让两个右括号匹配
而我们 为什么要匹配？
因为要求一条回路，$b1==2$ $and$ $b2==1$和$b1==1$ $and$ $b2==2$的状态产生的结果截然不同(请看下文)，必须要注意 **括号匹配**
$(5)$ $b1==2$ $and$ $b2==2$ 和上面一样$O(m)$往左扫找另一边的左括号，让两个左括号匹配，脑补吧$qwq$
$(6)$ $b1==2$ $and$ $b2==1$ 直接删掉两个插头(闭合)就好了，不需要处理另一端的插头了，两边的插头会自动匹配$(1212->1002)$
 
$(7)$ $b1==1$ $and$ $b2==2$出现这种状态，达到了最终闭合状态，当前点为终点更新答案，否则状态不合法
本题利用$hash$和滚动节省空间，为方便与快捷用位运算实现四进制，具体细节看代码，
或许你看到每行之间多了一个这样的状态转移，在此提一下，相当于到每行第一个格子时，前面补一个空插头，剩下的部分从上一行最后一个格子那里直接搬过来
```cpp
for(LL j=1;j<=cnt[now];++j)
que[now][j]<<=2;
```
可能你会想，这八种情况，真的能把所有情况全表示出来吗，我们来看一张图
这种情况怎么来呢，是由$(3,4)$的下插头向下延伸与$(3,2)$的下插头一直向右延伸交由$(4,3)$
然后由$(4)$,$(5)$,$(6)$,$(7)$的某种转移而来
当然，可以严格证明出所有状态都能有上面的八种情况得到，因为只需要所有状态都在情况内
### **My complete code：**
```cpp
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long LL;
const LL maxn=13;
const LL hs=299987;
LL n,m,ex,ey,now,last,ans;
LL a[maxn][maxn],head[300000],next[2<<24],que[2][2<<24],val[2][2<<24],cnt[2],inc[13];
inline void init(){
scanf("%lld%lld",&n,&m);
for(LL i=1;i<=n;++i){
char s[100];
scanf(" %s",s+1);
for(LL j=1;j<=m;++j){
if(s[j]=='.'){
a[i][j]=1;
ex=i; ey=j;
}
}
}
inc[0]=1;
for(LL i=1;i<=13;++i)
inc[i]=inc[i-1]<<2;
}
inline void insert(LL bit,LL num){
LL u=bit%hs+1;
for(LL i=head[u];i;i=next[i]){
if(que[now][i]==bit){
val[now][i]+=num;
return;
}
}
next[++cnt[now]]=head[u];
head[u]=cnt[now];
que[now][cnt[now]]=bit;
val[now][cnt[now]]=num;
}
inline void work(){
cnt[now]=1; val[now][1]=1; que[now][1]=0;
for(LL i=1;i<=n;++i){
for(LL j=1;j<=cnt[now];++j)
que[now][j]<<=2;
for(LL j=1;j<=m;++j){
memset(head,0,sizeof(head));
last=now; now^=1;
cnt[now]=0;
for(LL k=1;k<=cnt[last];++k){
LL bit=que[last][k],num=val[last][k];
LL b1=(bit>>((j-1)*2))%4,b2=(bit>>(j*2))%4;
if(!a[i][j]){
if(!b1&&!b2)
insert(bit,num);
}else if(!b1&&!b2){
if(a[i+1][j]&&a[i][j+1])
insert(bit+inc[j-1]+inc[j]*2,num);
}else if(!b1&&b2){
if(a[i][j+1])
insert(bit,num);
if(a[i+1][j])
insert(bit-inc[j]*b2+inc[j-1]*b2,num);
}else if(b1&&!b2){
if(a[i+1][j])
insert(bit,num);
if(a[i][j+1])
insert(bit-inc[j-1]*b1+inc[j]*b1,num);
}else if(b1==1&&b2==1){
LL k1=1;
for(LL l=j+1;l<=m;++l){
if((bit>>(l*2))%4==1)
++k1;
if((bit>>(l*2))%4==2)
--k1;
if(!k1){
insert(bit-inc[j]-inc[j-1]-inc[l],num);
break;
}
}
}else if(b1==2&&b2==2){
LL k1=1;
for(LL l=j-2;l>=0;--l){
if((bit>>(l*2))%4==1)
--k1;
if((bit>>(l*2))%4==2)
++k1;
if(!k1){
insert(bit-inc[j]*2-inc[j-1]*2+inc[l],num);
break;
}
}
}else if(b1==2&&b2==1){
insert(bit-inc[j-1]*2-inc[j],num);
}else if(i==ex&&j==ey){
ans+=num;
}
}
}
}
}
int main(){
init();
work();
printf("%lld",ans);
return 0;
}
```
来放松一下吧
## [P5074 Eat the Trees](https://www.luogu.org/problemnew/show/P5074)
其实对于刚学插头dp也较难完成，但建议读者先独立思考
题目大意
>给出n*m的方格，有些格子不能铺线，其它格子必须铺，可以形成多个闭合回路。问有多少种铺法？n,m(2<=n,m<=12)
上一题的转化题，可以形成多个回路了，$b1$ $and$ $b2$时虽然$1$与$2$ **实际**上对整体情况有影响，但对状态转移无影响
怎么理解呢？上一题的括号匹配提过，再加上此题可以形成多条回路，所以实际情况肯定会有影响；至于状态转移，反正我们只需要把加方案数，自然无影响
此题不需要括号匹配，多条回路$b1$ $and$ $b2$实际闭合删插头，用二进制，$1$表示有插头，$0$表示无插头
ps：如果整个图都没有1，只有0，也算一种合法方案！
上一题放的是hash代码，为了让大家更熟悉，这里放个费空间的
```cpp
#include<cstring>
#include<string>
#include<cstdio>
using namespace std;
typedef long long LL;
const LL maxn=13;
const LL hs=299987;
LL n,m,now,last,ans,kase,T,M,up;
LL a[maxn][maxn],inc[maxn],dp[maxn][maxn][1<<maxn];
inline LL read(){
LL x=0,f=1; char c=getchar();
while(c<'0'||c>'9'){
if(c=='-') f=-1; c=getchar();
}
while(c>='0'&&c<='9'){
x=x*10+c-'0'; c=getchar();
}return x*f;
}
inline void solve(){
memset(dp,0,sizeof(dp));
dp[0][m][0]=1;
for(LL i=1;i<=n;++i){
for(LL j=0;j<=up;++j)
dp[i][0][j<<1]=dp[i-1][m][j];
for(LL j=1;j<=m;++j){
for(LL k=0;k<=up;++k){
LL bit=k,num=dp[i][j-1][k];
LL b1=(bit>>(j-1))&1,b2=(bit>>(j))&1;
if(!a[i][j]){
if(!b1&&!b2)
dp[i][j][bit]+=num;
}else if(!b1&&!b2)
dp[i][j][bit+inc[j-1]+inc[j]]+=num;
else if(!b1&&b2){
if(a[i][j+1])
dp[i][j][bit]+=num;
if(a[i+1][j])
dp[i][j][bit+inc[j-1]-inc[j]]+=num;
}else if(b1&&!b2){
if(a[i][j+1])
dp[i][j][bit-inc[j-1]+inc[j]]+=num;
if(a[i+1][j])
dp[i][j][bit]+=num;
}else
dp[i][j][bit-inc[j-1]-inc[j]]+=num;
}
}
}
//printf("Case %lld: There are %lld ways to eat the trees.\n",++kase,dp[n][m][0]);
printf("%lld\n",dp[n][m][0]);
}
int main(){
T=read();
inc[0]=1;
for(LL i=1;i<=13;++i)
inc[i]=inc[i-1]<<1;
while(T--){
n=read(); m=read();
up=(1<<(m+1))-1;
for(LL i=1;i<=n;++i)
for(LL j=1;j<=m;++j)
a[i][j]=read();
solve();
}
return 0;
}/*
*/
```
## [P3886 [JLOI2009]神秘的生物](https://www.luogu.org/problemnew/show/P3886)
题目大意
>n*n的带权网格，求某个联块的最大和 n<=9
这里不需要形成回路，而是经典的联通块题，上面的方法无用武之地了(判断联通)，通常我们采取最小表示法
$n<=9$用$8$进制(与四进制同理)表示，同一个联通块用相同数字表示，数字也只是暂时的而已，选择一个块后，由于可能会改变联通状态，要重新标记数字
此题的轮廓线有所不同，因为两相邻块均选是直接联通的，如下图
 
每个方格有两种基本状态
**不选**
当然得考虑状态合理，无下插头或下插头所在联通块还有其他插头，否则下插头被孤立而不形成联通块了
大家发现没有？
这里每个状态仅合理而已，并不能确定这是可取的最终状态，因为最后得保证只有一个联通块(其实上文也)，详细请看$update$
那为什么不考虑右插头呢？而要判断下插头呢？
因为下插头以后再也不会判断了，所以要考虑状态合理，右插头到下一行自然会考虑状态
右插头来自上一个转移状态，很可能形成新块$7$，故这样转移条件会变得严苛，最终答案通常会小于正确答案
**选**
$(1)$ $!b1$ $and$ $!b2$单独形成新块，此块命名为7
$(2)$ $b1$ $or$ $b2$ 此块与插头相连，更新联通块状态，这就是伟大的最小表示法
```cpp
s[j]=max(b1,b2);
for(LL l=1;l<=m;++l)
if(s[l]&&s[l]==min(b1,b2))
s[l]=max(b1,b2);
```
$Ps$：在$updateup$时，只有当存在唯一联通块时才$update$ $ans$
### **My complete code：**
```cpp
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long LL;
const LL maxn=24;
const LL hs=299987;
LL n,ans=-2*1e9,now=0,last=1;
LL val[2][1<<maxn],que[2][1<<maxn],next[1<<maxn],head[300000],a[maxn][maxn],cnt[2],inc[maxn],s[maxn];
inline void insert(LL bit,LL num){
LL u=bit%hs+1;
for(LL i=head[u];i;i=next[i]){
if(que[now][i]==bit){
val[now][i]=max(val[now][i],num);
return;
}
}
next[++cnt[now]]=head[u];
head[u]=cnt[now];
que[now][cnt[now]]=bit;
val[now][cnt[now]]=num;
}
inline LL update(LL num){
LL belong[maxn];
memset(belong,0,sizeof(belong));
LL sum=0;
for(LL i=1;i<=n;++i)
if(s[i]){
if(belong[s[i]])
s[i]=belong[s[i]];
else
s[i]=belong[s[i]]=++sum;
}
LL bit=0;
for(LL i=1;i<=n;++i)
bit+=(s[i]<<inc[i-1]);
if(sum==1)
ans=max(ans,num);
return bit;
}
inline void get_bitset(LL bit){
for(LL i=1;i<=n;++i)
s[i]=(bit>>inc[i-1])%8;
}
inline void solve(){
insert(0,0);
for(LL i=1;i<=n;++i){
for(LL j=1;j<=n;++j){
swap(now,last);
cnt[now]=0;
memset(head,0,sizeof(head));
for(LL k=1;k<=cnt[last];++k){
get_bitset(que[last][k]);
LL b1=s[j-1],b2=s[j];
LL num=val[last][k];
LL sum=0;
s[j]=0;
for(LL l=1;l<=n;++l)
if(s[l]==b2)
++sum;
if(!b2 || sum)
insert(update(num),num);
num+=a[i][j];
get_bitset(que[last][k]);
if(!b1&&!b2)
s[j]=7;
else{
s[j]=max(b1,b2);
for(LL l=1;l<=n;++l)
if(s[l]&&s[l]==min(b1,b2))
s[l]=max(b1,b2);
}
insert(update(num),num);
}
}
}
}
int main(){
for(LL i=1;i<=10;++i)
inc[i]=i*3;
scanf("%lld",&n);
for(LL i=1;i<=n;++i)
for(LL j=1;j<=n;++j)
scanf("%lld",&a[i][j]);
solve();
printf("%lld",ans);
return 0;
}
```
## [P3190 [HNOI2007]神奇游乐园](https://www.luogu.org/problemnew/show/P3190)
题目大意
>n*m的带权方格，求最大权回路 2<=n<=100，2<=m<=6
和模板题差不多，在$insert$时加一个最大值，自己写一遍吧，相信你能$A$掉的
### **核心代码：**
```cpp
inline void insert(LL bit,LL num){
LL u=bit%hs+1;
for(LL i=head[u];i;i=next[i])
if(que[now][i]==bit){
val[now][i]=max(val[now][i],num);
return;
}
next[++cnt[now]]=head[u];
head[u]=cnt[now];
que[now][cnt[now]]=bit;
val[now][cnt[now]]=num;
}
```
${}$
${}$
以下这题由于**斯坦纳树**做法更简单，不作例题讲重点讲，稍微提怎么求方案
## [P4294 [WC2008]游览计划](https://www.luogu.org/problemnew/show/P4294)
题目大意
>n*m的带权网格，求联通k个方格的最小权联通块方案（求某个方案而非方案数） n<=10 m<=10 k<=10
$road[now][bit]=$++$tot$表示$val[now][val]$最小时的状态，和$val$与$que$一样是滚动数组，因为之后就不需要了
$w[tot]$表示此时选或不选，$pre[tot]$表示上一个点的$w$下标，方便输出方案数，在更新成功$val[now][val]$时同时更新
### **Insert:**
```cpp
inline void insert(LL y,LL pe,LL bit,LL num){
LL u=bit%hs+1;
for(LL i=head[u];i;i=next[i])
if(que[now][i]==bit){
if(val[now][i]>num){
val[now][i]=num;
pre[road[now][i]]=pe;
w[road[now][i]]=(bit>>inc[y-1])%8;
if(f)
tmp=road[now][i];
}
return;
}
next[++cnt[now]]=head[u];
head[u]=cnt[now];
que[now][cnt[now]]=bit;
val[now][cnt[now]]=num;
road[now][cnt[now]]=++tot;
pre[tot]=pe;
w[tot]=(bit>>inc[y-1])%8;
if(f)
tmp=tot;
}
```
## [P3272 [SCOI2011]地板](https://www.luogu.org/problemnew/show/P3272)
显然，$L$型地板：拐弯且仅拐弯一次。
发现没有，一个存在的插头只有两种状态：拐弯过和没拐弯过，因此我们这样定义插头：
0表没有插头，1表没拐过的插头，2表已经拐过的插头。$b1$代表当前点的右插头,$b2$代表当前点的下插头
那么会有下面的几种情况：
$(1)$ $b1==0$ $and$ $b2==0$
1. $b1$添加一个插头$1$，相当于加入一个从该点出发向下的$L$地板
1. $b2$添加一个插头$1$，相当于加入一个从该点出发向右的$L$地板
1. $b1$,$b2$均改成插头$2$，相当于该点作为$L$地板的拐弯处
$(2)$ $b1==0$ $and$ $b2==1$
1. $b1=1$,$b2=0$ 相当于继续直走，不拐弯，所以$b1$转为$b2$，$b2$此时无插头了
1. $b1=0$,$b2=2$ 相当于向右拐
$(3)$ $b1==1$ $and$ $b2==0$
跟$(2)$差不多
$(4)$ $b1==0$ $and$ $b2==2$
1. 结束，将插头去掉，如果为终点更新答案，否则去掉插头则可
1. $b2$向下延伸，$b1==2$ $ $ $b2==0$
$(5)$ $b1==2$ $and$ $b2==0$
跟$(4)$差不多
$(6)$ $b1==1$ $and$ $b2==1$
1. 直接删去就好了，相当于两个没拐过的插头会和，形成$L$拐弯交界处
做完一个题当然得总结一下：这题虽然与前面回路的题不同，看似无从下手，但从$L$型的性质，考虑状态，全部考虑到，自然就$A$掉了
## [P2337 [SCOI2012]喵星人的入侵](https://www.luogu.org/problemnew/show/P2337)
这题深刻得体会到了插头dp的毒瘤$emmm$
这里在联通路径情况下，增加了特殊限制，相当于每个点的权值由周围八连通块炮台数量决定
要求最后方案最小路径最大，而可以放无限个障碍，显然，为了简化状态，我们最后留一条路径就好了
这里一种状态由什么来表示？插头，路径状态，已放炮台数量
和原来好像完全不一样了，别担心，多开几个数组存状态，把所有的状态全部考虑一遍就好了嘛
以下借鉴了**dalao[@ComeIntoPower](https://www.luogu.org/space/show?uid=11751)**的思想与代码
**重点：**
这里的插头状态：$0$空插头 $1$左插头 $2$右插头 $3$独立插头
独立插头不知道意思？其实之前算是已经接触过了，记不记得，在求最大联通块权，有一个新块$7$，**差不多**就是这个意思
由于起点终点只延伸一个方向，不参与括号匹配，所以单独标记为3
插头轮廓状态表示如下
棋盘轮廓状态：$0$障碍 $1$路径 $3$炮台，状态表示如下，故判断是提取八联通块中已确定的四块
$Conn$函数为当前的纵坐标为$u$，插头状态为$st$，将插头$op$另一端改成$v$
```cpp
LL Conn(LL st,LL op,LL u,LL v)
```
$nxt$函数表将当前棋盘状态换完$a$
```cpp
nxt(a) (stb-(yb<<bit(j+1))+((a)<<bit(j+1)))
```
滚动数组存三种小状态
本题状态较多，详情请看完整代码(内有注释),相信你能看懂
### **My complete code：**
```cpp
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define bit(x) ((x)<<1)
#define nxt(a) (stb-(yb<<bit(j+1))+((a)<<bit(j+1)))
using namespace std;
typedef long long LL;
const LL maxn=10000000;
const LL hs=299987;
LL n,m,now,last,K,ans;
LL cnt[2],val[2][maxn],que[2][maxn],nxt[maxn],stA[2][maxn],stB[2][maxn],stC[2][maxn],head[300000];
char a[30][30],tmp[30][30];
LL Hash(LL x,LL y,LL z){
return ((((x)<<16|y)<<4|z));
}
void Add(LL x,LL y,LL z,LL w){
LL u=Hash(x,y,z)%hs+1,h=Hash(x,y,z);
for(LL i=head[u];i;i=nxt[i])
if(que[now][i]==h){
val[now][i]=max(val[now][i],w);
return;
}
nxt[++cnt[now]]=head[u],
head[u]=cnt[now],
val[now][cnt[now]]=w,
que[now][cnt[now]]=h,
stA[now][cnt[now]]=x,
stB[now][cnt[now]]=y,
stC[now][cnt[now]]=z;
}
LL Conn(LL st,LL op,LL u,LL v){
if(op==1){
LL b=1;
for(;;++u){
LL p=(st>>bit(u))&3;
if(p==1)
b++;
if(p==2)
b--;
if(!b)
return st-(p<<bit(u))+(v<<bit(u));
}
} else {
LL b=1;
for(;;--u){
LL p=(st>>bit(u))&3;
if(p==2)
b++;
if(p==1)
b--;
if(!b)
return st-(p<<bit(u))+(v<<bit(u));
}
}
}
inline void Solve(){
now=0,last=1;
val[now][++cnt[now]]=0;
for(LL i=0;i<n;++i){
for(LL j=1;j<=cnt[now];++j)
stA[now][j]<<=2,
stB[now][j]=(stB[now][j]-(((stB[now][j]>>bit(m+1))&3)<<bit(m+1)))<<2;
for(LL j=0;j<m;++j){
swap(now,last);
memset(head,0,sizeof(head));
cnt[now]=0;
for(LL s=1;s<=cnt[last];++s){
LL sta=stA[last][s],
stb=stB[last][s],
k=stC[last][s],
w=val[last][s];
if(sta>=(1<<bit(m+1)))//上一行是否最后添加插头，添加则超出格限制，跳过
continue;
LL b1,b2,xb,yb,zb,pb;
b1=sta>>bit(j)&3,
b2=sta>>bit(j+1)&3;
xb=stb>>bit(j)&3,
yb=stb>>bit(j+1)&3;
zb=stb>>bit(j+2)&3,
pb=stb>>bit(j+3)&3;
LL nsta=sta-(b1<<bit(j))-(b2<<bit(j+1));
if((xb==1&&!b1)||(zb==1&&!b2)){//不走就拦
if(!b1&&!b2){
Add(sta,nxt(0),k,w);//障碍
w+=(xb==1)+(yb==1)+(zb==1)+(pb==1);
if(k<K&&a[i][j]=='.')
Add(sta,nxt(3),k+1,w);//炮台
}
}else if(a[i][j]=='#'){
if(!b1&&!b2)
Add(nsta,nxt(0),k,w);
}else if(a[i][j]=='.'){
LL w1=w+(xb==1)+(yb==1)+(zb==1)+(pb==1),
w2=w;
w+=(xb==3)+(yb==3)+(zb==3)+(pb==3);
if(!b1&&!b2){
if(k<K)
Add(nsta,nxt(3),k+1,w1);//记录对走过的路径造成的影响
Add(nsta+(1<<bit(j))+(2<<bit(j+1)),nxt(1),k,w);//加两个插头
Add(nsta,nxt(0),k,w2);//不走
}else if(!b1){// 延伸
Add(nsta+(b2<<bit(j)),nxt(1),k,w);
Add(nsta+(b2<<bit(j+1)),nxt(1),k,w);
}else if(!b2){//延伸
Add(nsta+(b1<<bit(j)),nxt(1),k,w);
Add(nsta+(b1<<bit(j+1)),nxt(1),k,w);
}else if(b1==2&&b2==1){//合并
Add(nsta,nxt(1),k,w);
}else if(b1==1&&b2==1){//找到右替换成左
Add(Conn(nsta,1,j,1),nxt(1),k,w);
}else if(b1==2&&b2==2){//找到左替换成右
Add(Conn(nsta,2,j,2),nxt(1),k,w);
}else if(b1==3&&b2==1){//找到右替换成独立
Add(Conn(nsta,1,j,3),nxt(1),k,w);
}else if(b1==3&&b2==2){//找到左替换成独立
Add(Conn(nsta,2,j,3),nxt(1),k,w);
}else if(b1==1&&b2==3){//找到右替换成独立
Add(Conn(nsta,1,j,3),nxt(1),k,w);
}else if(b1==2&&b2==3){//找到左替换成独立
Add(Conn(nsta,2,j,3),nxt(1),k,w);
}else if(b1==3&&b2==3){//合并
Add(nsta,nxt(1),k,w);
}
}else if(a[i][j]=='S'||a[i][j]=='T'){
w+=(xb==3)+(yb==3)+(zb==3)+(pb==3);
if(a[i][j]=='S'&&!b1&&!b2){//起点且无插头
Add(sta+(3<<bit(j)),nxt(1),k,w);
Add(sta+(3<<bit(j+1)),nxt(1),k,w);//延伸
}else if(a[i][j]=='T'&&!b1&&!b2){//终点且无插头
Add(sta+(3<<bit(j)),nxt(1),k,w);
Add(sta+(3<<bit(j+1)),nxt(1),k,w);//延伸
}else if(!b1&&b2!=3&&b2!=0){//有非独立插头改成独立插头
Add(Conn(nsta,b2,j,3),nxt(1),k,w);
}else if(!b2&&b1!=3&&b1!=0){//有非独立插头改成独立插头
Add(Conn(nsta,b1,j,3),nxt(1),k,w);
}else if(!b1&&b2==3){//两端已连接，不需要再添加
Add(nsta,nxt(1),k,w);
}else if(b1==3&&!b2){////两端已连接，不需要再添加
Add(nsta,nxt(1),k,w);
}
}
}
}
}
}
int main(){
scanf("%lld%lld%lld",&n,&m,&K);
for(LL i=0;i<n;++i)
scanf(" %s",tmp[i]);
if(n<m){
for(LL i=0;i<n;++i)
for(LL j=0;j<m;++j)
a[j][i]=tmp[i][j];
swap(n,m);
}else{
for(LL i=0;i<n;++i)
for(LL j=0;j<m;++j)
a[i][j]=tmp[i][j];
}
Solve();
for(LL i=1;i<=cnt[now];++i)
if(!stA[now][i])
ans=max(ans,val[now][i]);
printf("%lld\n",ans);
return 0;
}
```