本文版权归ljh2000和博客园共有，欢迎转载，但须保留此声明，并给出原文链接，谢谢合作。
本文作者：ljh2000
作者博客：http://www.cnblogs.com/ljh2000-jump/
转载请注明出处，侵权必究，保留最终解释权！
Description
.jpg)
Input
第一行有两个整数，N和 M，描述方块的数目。
接下来 N行， 每行有 M 个非负整数， 如果该整数为 0， 则该方块为一个景点；
否则表示控制该方块至少需要的志愿者数目。 相邻的整数用 （若干个） 空格隔开，
行首行末也可能有多余的空格。
Output
由 N + 1行组成。第一行为一个整数，表示你所给出的方案
中安排的志愿者总数目。
接下来 N行，每行M 个字符，描述方案中相应方块的情况：
z ‘_’（下划线）表示该方块没有安排志愿者；
z ‘o’（小写英文字母o）表示该方块安排了志愿者；
z ‘x’（小写英文字母x）表示该方块是一个景点；
注：请注意输出格式要求，如果缺少某一行或者某一行的字符数目和要求不
一致（任何一行中，多余的空格都不允许出现） ，都可能导致该测试点不得分。
Sample Input
4 4
0 1 1 0
2 5 5 1
1 5 5 1
0 1 1 0
0 1 1 0
2 5 5 1
1 5 5 1
0 1 1 0
Sample Output
6
xoox
___o
___o
xoox
xoox
___o
___o
xoox
HINT
对于100%的数据，N,M,K≤10，其中K为景点的数目。输入的所有整数均在[0,2^16]的范围内
正解：斯坦纳树
解题报告：
斯坦纳树入门题…
考虑我把这些关键点用二进制状态表示，那么我可以用状压的方式来转移。
f[i][j][s]表示连通性至少为s，且联通出来的树的根在(i,j)的最优值，转移的话就是枚举s的子集，然后将s-子集和子集两个部分合并。
还有一种转移，同状态之间的连通树换根，同层之间SPFA转移即可。
这道题需要记录方案，记一下每个状态的pre前驱即可。
//It is made by ljh2000
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <ctime>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <complex>
using namespace std;
typedef long long LL;
const int MAXN = 12;
const int MAXS = 1024;
const int MAXM = 1000011;
int n,m,k,ju[MAXN][MAXN],S,dui[MAXM][2],head,tail,a[MAXN][MAXN];
int f[MAXN][MAXN][MAXS];//f[i][j][s]表示连通性至少为s，且联通出来的树的根在(i,j)的最优值
int pre[MAXN][MAXN][MAXS][3];//记录前驱状态
bool vis[MAXN][MAXN];
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
inline int getint(){
int w=0,q=0; char c=getchar(); while((c<'0'||c>'9') && c!='-') c=getchar();
if(c=='-') q=1,c=getchar(); while (c>='0'&&c<='9') w=w*10+c-'0',c=getchar(); return q?-w:w;
}
inline void print(){
for(int i=1;i<=n;i++) {
for(int j=1;j<=m;j++) {
if(ju[i][j]==0) printf("x");
else if(a[i][j]) printf("o");
else printf("_");
}
puts("");
}
}
inline void dfs(int x,int y,int s){
if(x==0 || y==0) return ;
a[x][y]=1; dfs(pre[x][y][s][0],pre[x][y][s][1],pre[x][y][s][2]);
//有两个方向!!!
if(pre[x][y][s][0]==x && pre[x][y][s][1]==y) dfs(x,y,s-pre[x][y][s][2]);//两个状态在共用根的情况下进行合并
}
inline void SPFA(int s){
head=tail=0; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(f[i][j][s]!=f[0][0][0]) { vis[i][j]=1; dui[++tail][0]=i; dui[tail][1]=j; }
int ux,uy,nowx,nowy;
while(head<tail) {
head++; ux=dui[head][0]; uy=dui[head][1]; vis[ux][uy]=0;
for(int i=0;i<4;i++) {
nowx=ux+dx[i]; nowy=uy+dy[i]; if(nowx<=0 || nowy<=0 || nowx>n || nowy>m/*!!!*/) continue;
if(f[nowx][nowy][s]>f[ux][uy][s]+ju[nowx][nowy]) {
f[nowx][nowy][s]=f[ux][uy][s]+ju[nowx][nowy];
pre[nowx][nowy][s][0]=ux;
pre[nowx][nowy][s][1]=uy;
pre[nowx][nowy][s][2]=s;
if(!vis[nowx][nowy]) {
vis[nowx][nowy]=1;
dui[++tail][0]=nowx;
dui[tail][1]=nowy;
}
}
}
}
}
inline void work(){
n=getint(); m=getint();
memset(f,0x3f,sizeof(f));
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++) {
ju[i][j]=getint();
if(ju[i][j]==0) f[i][j][(1<<k)]=0,k++;
}
S=(1<<k)-1; int now;
if(k==0) {
for(int i=1;i<=n;i++) {
for(int j=1;j<=m;j++)
if(ju[i][j]) printf("_");
puts("");
}
return ;
}
for(int s=1;s<=S;s++) {
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
for(int from=(s-1)&s;from;from=(from-1)&s) {//枚举子集
if(f[i][j][from]==f[0][0][0] || f[i][j][s-from]==f[0][0][0]) continue;
now=f[i][j][from]+f[i][j][s-from]-ju[i][j];
if(now<f[i][j][s]) {
f[i][j][s]=now;
pre[i][j][s][0]=i; pre[i][j][s][1]=j; pre[i][j][s][2]=from;
}
}
SPFA(s);
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(ju[i][j]==0) {
printf("%d
",f[i][j][S]);
dfs(i,j,S);
print();
return ;
}
}
int main()
{
work();
return 0;
}