斯坦纳树早在6月份吧小狗就讲过了然而当时并没有填这个坑

感觉写起来还是很轻松愉快的不过虽然这么说还是被细节卡了好久

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 13
#define M 1024
#define INF 0x3f7f7f7f
int v[N][N],st,S,la[N][N][M][4],li[M*M][3];
int s[N][N][M],a[N][2],n,m;bool b[N][N][M];
const int dir[4][2]={{0,1},{1,0},{-1,0},{0,-1}};
inline int Read()
 {
 	int x=0;char y;
 	do y=getchar(); while (y<'0'||y>'9');
 	do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
 	return x;
 }
inline void Trans(int x,int y,int z,int o,int p,int *ri)
 {
 	if (!o||!p||o>n||p>m||v[o][p]+s[x][y][z]>=s[o][p][z])
 	  return;
 	s[o][p][z]=v[o][p]+s[x][y][z];
 	la[o][p][z][0]=x;la[o][p][z][1]=y;la[o][p][z][2]=z;
 	la[o][p][z][3]=0;
 	if (!b[o][p][z])
 	  (*ri)++,b[li[*ri][0]=o][li[*ri][1]=p][li[*ri][2]=z]=1;
 }
void SPFA(int t)
 {
 	int le=1,ri=0;
 	for (int i=1;i<=n;i++)
 	 for (int j=1;j<=m;j++)
 	  if (s[i][j][t]!=INF)
 	  	li[++ri][0]=i,li[ri][1]=j,li[ri][2]=t,
 	    b[i][j][t]=1;
 	for (;le<=ri;le++)
 	 {
 	 	int q=li[le][0],w=li[le][1],e=li[le][2];
 	 	for (int i=0;i<4;i++)
 	 	  Trans(q,w,e,dir[i][0]+q,dir[i][1]+w,&ri);
 	 	b[q][w][e]=0;
 	 }
 	return;
 }
void Solve()
 {
 	for (int i=1;i<=n;i++)
 	 for (int j=1;j<=m;j++)
 	  for (int k=1;k<S;k++)
 	  	s[i][j][k]=INF;
 	for (int i=1;i<=n;i++)
 	 for (int j=1;j<=m;j++)
 	   s[i][j][0]=v[i][j];
 	for (int i=1;i<=st;i++)
 	  s[a[i][0]][a[i][1]][1 << i - 1]=0;
 	for (int t=0;t<S;t++)
 	 {
 	 	for (int i=(t-1)&t;i;i=(i-1)&t)
 	 	 for (int j=1;j<=n;j++)
 	 	  for (int k=1;k<=m;k++)
 	 	   if (s[j][k][t]>s[j][k][i]+s[j][k][t-i]-v[j][k])
 	 	    {
 	 	       s[j][k][t]=s[j][k][i]+s[j][k][t-i]-v[j][k];
 	 	       la[j][k][t][0]=j;la[j][k][t][1]=k;
 	 	       la[j][k][t][2]=i;la[j][k][t][3]=t-i;
 	 	    }
 	 	SPFA(t);
 	 }
 }
void DFS(int x,int y,int z)
 {
 	if (v[x][y]) v[x][y]=-1;
 	if (!la[x][y][z][0]) return;
 	if (la[x][y][z][3])
 	  DFS(x,y,la[x][y][z][2]),DFS(x,y,la[x][y][z][3]);else
 	  DFS(la[x][y][z][0],la[x][y][z][1],la[x][y][z][2]);
 }
void Print()
 {
 	DFS(a[1][0],a[1][1],S-1);
 	printf("%d\n",s[a[1][0]][a[1][1]][S-1]);
 	for (int i=1;i<=n;i++)
 	 {
 	 	for (int j=1;j<=m;j++)
 	   	 if (!v[i][j]) putchar('x');else
 	   	 if (v[i][j]==-1) putchar('o');else
 	   	   putchar('_');
 	   	puts("");
 	 }
 }
int main()
 {
 	n=Read();m=Read();
 	for (int i=1;i<=n;i++)
 	 for (int j=1;j<=m;j++)
 	  {
 	  	 v[i][j]=Read();
 	  	 if (!v[i][j])
 	  	   a[++st][0]=i,a[st][1]=j;
 	  }
 	S=1 << st;
 	Solve();
 	Print();
 	return 0;
 }