第一次接触连通块的插头dp
用最小表示法表示每个连通块，由于数据范围知道连通块最多为5个，所以用8进制即可
状态转移照模板推一推
需要注意的是对于上面来的连通块如果不连通的话需要考虑其是否还有其它地方与下方相连，如果没有则必须在此点往下相连，否则上方那个连通块将被孤立，不符合题意
但是左边而来的连通块却不需要考虑，原因是左方格子在下一行时会再次考虑其连通性，而上方却是最后一次考虑了。
点击查看代码
#include<bits/stdc++.h>
#include<unordered_map>
#define int long long
#define inf 1e18
#define inc 0xcfcfcfcf
#define N 17
#define M 500007
#define mod 1000000007
//#pragma GCC optimize(2)
//#pragma GCC optimize(3)
using namespace std;
int T=1,n,m,ans=-inf;
int g[N][N];
int vis[N];
unordered_map<int,int> f[2];
inline int Read()
{
char ch=getchar();bool f=0;int x=0;
for(;!isdigit(ch);ch=getchar())if(ch=='-')f=1;
for(;isdigit(ch);ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
if(f==1)x=-x;return x;
}
int Get_s(int num,int pos){return (num<<(pos*3));}
void Insert(int pos,int S,int val)
{
memset(vis,0,sizeof(vis));
int cnt=0,S1=0;
for(int i=0;i<n;++i)
{
int now=(S>>(i*3))&7;
if(!now)
continue;
if(!vis[now])
vis[now]=++cnt,now=cnt;
else
now=vis[now];
S1^=Get_s(now,i);
}
if(cnt==1)
ans=max(ans,val);
if(f[pos].find(S1)==f[pos].end())
f[pos][S1]=val;
else
f[pos][S1]=max(f[pos][S1],val);
}
int Ctdp()
{
int now=0;
int mxn=(1<<(n*3))-1;
f[now][0]=0;
f[1].clear();
for(int i=1;i<=n;++i)
{
for(int j=1;j<=n;++j)
{
int nxt=now^1;
for(auto k:f[now])
{
int S=k.first,val=k.second;
int ctr=(S>>((j-1)*3))&7;
int ctl=0;
if(j!=1)
ctl=(S>>((j-2)*3))&7;
if(!ctl&&!ctr)
{
Insert(nxt,S,val);
Insert(nxt,S^Get_s(7,j-1),val+g[i][j]);
}
if(ctl&&!ctr)
{
Insert(nxt,S^Get_s(ctl,j-1),val+g[i][j]);
Insert(nxt,S,val);
}
if(!ctl&&ctr)
{
Insert(nxt,S,val+g[i][j]);
int cnt=0;
for(int p=0;p<n;++p)
{
int pos=(S>>(p*3))&7;
if(pos==ctr)
++cnt;
}
if(cnt>=2)
Insert(nxt,S^Get_s(ctr,j-1),val);
}
if(ctl&&ctr)
{
int cnt=0;
for(int p=0;p<n;++p)
{
int pos=(S>>(p*3))&7;
if(pos==ctr)
++cnt;
}
if(cnt>=2)
Insert(nxt,S^Get_s(ctr,j-1),val);
int S1=S;
if(ctl!=ctr)
for(int p=0;p<n;++p)
{
int pos=(S>>(p*3))&7;
if(pos==ctr)
S1^=Get_s(ctr,p)^Get_s(ctl,p);
}
Insert(nxt,S1,val+g[i][j]);
}
}
f[now].clear();
now^=1;
}
}
return 0;
}
bool Solve()
{
//freopen("test.in","r",stdin);
n=Read();
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
g[i][j]=Read(),ans=max(ans,g[i][j]);
Ctdp();
printf("%lld\n",ans);
return true;
}
signed main()
{
//T=Read();
while(T--)
if(!Solve())
printf("-1\n");
return 0;
}
/*
3
16 -16 2
15 0 0
-11 8 8
3
1 -5 1
-5 1 1
1 1 1
*/