斯坦纳树

Steiner树（斯坦纳树）：4个村庄坐落在欧⼏⾥得平⾯上⼀个单位正⽅形的4个
顶点上。要求⽤最短的公路⽹把它们连接起来，使得每对村庄之间都有⼀条连通
的路径。求这样⼀个⽹络。
提示：可以先考虑三个村庄的情况，然后扩展⾄四个村庄。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
#define N 15
const int INF=0x3f3f3f3f;
int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
struct node{
	int x,y,s;
	node(){}
	node(int a,int b,int c){x=a;y=b;s=c;}
}u,v;
int f[N][N][1<<10];
node pre[N][N][1<<10],pos[N];
int a[N][N],ans[N][N];
queue<node> q;bool inq[N][N];
void dfs(node i)
{
	if(!i.x)return;
	ans[i.x][i.y]=1;
	node j=pre[i.x][i.y][i.s];
	dfs(j);
	if(i.x==j.x&&i.y==j.y)dfs(node(i.x,i.y,i.s^j.s));
}
int main()
{
	int n,m,k=0,i,j,s,t,l;
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++){
		for(j=1;j<=m;j++){
			scanf("%d",&a[i][j]);
			if(!a[i][j]){k++;pos[k]=node(i,j,0);}
		}
	}
	memset(f,0x3f,sizeof(f));
	int all=(1<<k)-1;
	for(i=1;i<=n;i++)for(j=1;j<=m;j++)f[i][j][0]=0;
	for(i=1;i<=k;i++)f[pos[i].x][pos[i].y][1<<(i-1)]=0;
	for(s=1;s<=all;s++){
		for(i=1;i<=n;i++)for(j=1;j<=m;j++)
			for(t=(s-1)&s;t;t=(t-1)&s){
				if(f[i][j][s]>f[i][j][t]+f[i][j][s^t]-a[i][j]){
					f[i][j][s]=f[i][j][t]+f[i][j][s^t]-a[i][j];
					pre[i][j][s]=node(i,j,t);
				}
			}
		for(i=1;i<=n;i++)for(j=1;j<=m;j++)if(f[i][j][s]<INF)
			q.push(node(i,j,s)),inq[i][j]=1;
		while(!q.empty()){
			u=q.front();q.pop();inq[u.x][u.y]=0;
			for(l=0;l<4;l++){
				v.x=u.x+dx[l];v.y=u.y+dy[l];v.s=u.s;
				if(v.x>0&&v.x<=n&&v.y>0&&v.y<=m){
					if(f[v.x][v.y][s]>f[u.x][u.y][s]+a[v.x][v.y]){
						f[v.x][v.y][s]=f[u.x][u.y][s]+a[v.x][v.y];
						pre[v.x][v.y][s]=u;
						if(!inq[v.x][v.y])q.push(v),inq[v.x][v.y]=1;
					}
				}
			}
		}
	}
	int mi=INF;node ss;
	for(i=1;i<=n;i++)for(j=1;j<=m;j++)
		if(f[i][j][all]<=mi){
			mi=f[i][j][all];
			ss=node(i,j,all);
		}
	printf("%d\n",mi);
	dfs(ss);
	for(i=1;i<=n;i++){
		for(j=1;j<=m;j++){
			if(!a[i][j])printf("x");
			else if(ans[i][j])printf("o");
			else printf("_");
		}
		printf("\n");
	}
}