不是很会呢，但似乎抄了题解后有点明白了
sol：状态DP显然，其实是要构建一棵最小生成树一样的东西，我自己的理解（可能不是很对哦希望多多指教）f[x][y][zt]就是到x，y这个点，状态为zt,时的最小代价于是有两种转移方法：一种是若zt1|zt2=zt且zt1&zt2==0,那么f[x][y][zt]=min(f[x][y][zt],f[x][y][zt1]+f[x][y][zt2]),第二种就是跑spfa,如x1,y1和x,y联通，f[x1][y1][zt''']=min(f[x1][y1][zt'''],f[x][y][zt]+v[x1][y1]) 看起来不是很难，实现起来对菜鸡来说可费劲了qaq
#include <queue>
#include <cstdio>
#include <cstring>
using namespace std;
const int N=,B=(<<),inf=1e7,dx[]={-,,,},dy[]={,,-,};
int n,m,f[N][N][B],v[N][N],tot=,SX,SY,inq[N][N],re[N][N];
queue<pair<int,int> >q;
struct node
{
int x,y,zt;
}pre[N][N][B];
inline void spfa(int zt)
{
int i,xx,yy; pair<int,int>pp;
while(!q.empty())
{
pp=q.front(); q.pop(); inq[pp.first][pp.second]=;
for(i=;i<;i++)
{
xx=pp.first+dx[i]; yy=pp.second+dy[i]; if(xx<||xx>n||yy<||yy>m)continue;
if(f[xx][yy][zt]>f[pp.first][pp.second][zt]+v[xx][yy])
{
f[xx][yy][zt]=f[pp.first][pp.second][zt]+v[xx][yy]; pre[xx][yy][zt]=(node){pp.first,pp.second,zt};
if(!inq[xx][yy]) q.push(make_pair(xx,yy)),inq[xx][yy]=;
}
}
}
}
inline void dfs(int x,int y,int zt)
{
if(!pre[x][y][zt].zt)return; re[x][y]=;
node tmp=pre[x][y][zt]; dfs(tmp.x,tmp.y,tmp.zt); if(tmp.x==x&&tmp.y==y)dfs(x,y,zt^tmp.zt);
}
int main()
{
int i,j,zt,zz; scanf("%d%d",&n,&m); memset(f,,sizeof f);
for(i=;i<=n;i++)
{
for(j=;j<=m;j++)
{
scanf("%d",&v[i][j]); if(!v[i][j]) f[i][j][<<tot]=,SX=i,SY=j,tot++;
}
}
for(zt=;zt<(<<tot);zt++)
{
while(!q.empty()) q.pop(); memset(inq,,sizeof inq);
for(i=;i<=n;i++)
{
for(j=;j<=m;j++)
{
for(zz=zt;zz;zz=zt&(zz-))
{
if(f[i][j][zt]>f[i][j][zz]+f[i][j][zt^zz]-v[i][j])
{
f[i][j][zt]=f[i][j][zz]+f[i][j][zt^zz]-v[i][j]; pre[i][j][zt]=(node){i,j,zz};
}
}if(f[i][j][zt]<inf) q.push(make_pair(i,j)),inq[i][j]=;
}
}spfa(zt);
}printf("%d\n",f[SX][SY][(<<tot)-]); dfs(SX,SY,(<<tot)-);
for(i=;i<=n;i++)
{
for(j=;j<=m;j++)
{
if(!v[i][j])putchar('x');else if(re[i][j])putchar('o');else putchar('_');
}puts("");
}return ;
}