斯坦纳树
斯坦纳树，是一种神奇的树。它支持在一个连通图上求包含若干个选定点的最小生成树。
前置算法：spfa+状压dp+dfs（大雾）
我们设$f[o][P]$为第$o$个点上状态为$P$的最小代价，其中状态使用二进制存储已经连接了多少个选定点。
初始化：显然对于每个选定点，$f[o][1<<k]=0$，$k$为该选定点在所有选定点中的编号。其他为$inf$
蓝后就是将状态从小到大枚举进行递推
$for(P=0;P<(1<<k);++P)$
对于每层递推，枚举所有点$1$~$o$；
我们先考虑这个点连接了2个不同连通块（链）的状况（并为spfa做好准备）
于是我们枚举$P$的真子集进行递推
$for(j=(P-1)\&P;j;j=(j-1)\&P)$
枚举真子集↑
$f[o][P]=min(f[o][P],f[o][j]+f[o][P$^$j]-val[o]);$
注意该式适用于计算点权，减去$val[o]$是去掉重复点权。如果计算边权需作修改。
但是这样显然远远不够。于是我们用$spfa$通过类似$dp$的形式处理好剩下的所有状况。
对于前面的$f[o][P]$，任何$f[o][P]<inf$都应作为每层spfa的起点（显然spfa也是每层执行）
在共$K$个给定点中，随意找一个给定点作为树根$rt$。
$ans=f[rt][(1<<K)-1]$
对于本题$(extra)$：输出一种方案
我们在每次更新$f[o][P]$时
用$fa[o][P]$记下$f[o][P]$从哪个状态推导而来
最后从树根$rt$用$dfs$倒推回去，更新答案即可。
void dfs(pii u,int o){//u:坐标
par G=fa[F(u)][o];
if(!G.se) return;
use[u.fi][u.se]=;
if(G.fi==u) dfs(u,o^G.se);//两个联通块合并而来，则要从两条路递推回去。
dfs(G.fi,G.se);
}
$code:$
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
typedef pair<int,int> pii;
typedef pair<pii,int> par;
#define mp make_pair
#define fi first
#define se second
int d1[]={,,,-};
int d2[]={,,-,};
int n,m,tot,k,inf,f[][],id[][],a[][];
bool in[][],use[][];
par fa[][]; pii rt;
queue <pii> h;
inline int F(pii x){return id[x.fi][x.se];}
void spfa(int o){
while(!h.empty()){
pii x=h.front(); h.pop(); in[x.fi][x.se]=;
for(int i=;i<;++i){
int r1=x.fi+d1[i],r2=x.se+d2[i],to=id[r1][r2];
if(r1<||r1>=n||r2<||r2>=m) continue;
if(f[to][o]>f[F(x)][o]+a[r1][r2]){
f[to][o]=f[F(x)][o]+a[r1][r2];
fa[to][o]=mp(x,o);
if(!in[r1][r2]) h.push(mp(r1,r2));
}
}
}
}
void dfs(pii u,int o){//逆推找可行方案
par G=fa[F(u)][o];
if(!G.se) return;
use[u.fi][u.se]=;//选择点u
if(G.fi==u) dfs(u,o^G.se);
dfs(G.fi,G.se);
}
int main(){
memset(f,,sizeof(f)); inf=f[][];
scanf("%d%d",&n,&m);
for(int i=;i<n;++i)
for(int j=;j<m;++j){
scanf("%d",&a[i][j]);
id[i][j]=++tot;
if(!a[i][j]) rt=mp(i,j),f[tot][<<k]=,++k;
}
for(int P=;P<(<<k);spfa(P),++P)//每层递推的最后来一次spfa
for(int x=;x<n;++x)
for(int y=;y<m;++y){
int o=id[x][y];
for(int j=(P-)&P;j;j=(j-)&P)//枚举真子集
if(f[o][P]>f[o][j]+f[o][P^j]-a[x][y]){
f[o][P]=f[o][j]+f[o][P^j]-a[x][y];
fa[o][P]=mp(mp(x,y),j);
}
if(f[o][P]<inf) h.push(mp(x,y)),in[x][y]=;//可行点都能spfa
}
printf("%d\n",f[F(rt)][(<<k)-]); dfs(rt,(<<k)-);
for(int i=;i<n;++i,printf("\n"))
for(int j=;j<m;++j){
if(!a[i][j]) printf("x");
else if(use[i][j]) printf("o");
else printf("_");
}
return ;
}