Description
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]的范围内
题解：
裸裸的斯坦纳树，只是多了要求具体方案。
将需要联通的景点是否在联通块中压缩为状态k。F[i,k]表示已i点为中心的联通块，包含的景点为状态k，所需要的最小费用。
对于相邻的点i,j，可进行这样的转移：F[i,x]+F[j,y]——>F[i,x xor y]与F[j,x xor y]。对此进行spfa，记录其是由哪两个情况转移来的。
为了减少复杂度，转移时保证x and y=0。
见证奇迹：
（其实有种更优的DP写法，外加PASCAL在BZOJ中不享有明显的O2优化）
代码：
const
fx:array[..]of longint=(-,,,);
fy:array[..]of longint=(,-,,);
var
i,j,k:longint;
n,m,ans1,ans2,cnt,s,e,fro1,fro2,to1,to2,pos:longint;
map,map2:array[..,..]of longint;
a:array[..,..,..,..]of longint;
bo:array[..,..,..]of longint;
f:array[..,..]of longint;
procedure ss(x,y,z:longint);
begin
map2[x,y]:=;
if(a[x,y,z,]=)or(a[x,y,z,]=)then exit;
ss(x,y,a[x,y,z,]);
ss(a[x,y,z,],a[x,y,z,],z xor a[x,y,z,]);
end;
procedure wh(x,y:longint);
begin
if x>cnt then
begin
if a[fro1,fro2,pos,]+a[to1,to2,y,]<a[to1,to2,pos or y,] then
begin
a[to1,to2,pos or y,]:=a[fro1,fro2,pos,]+a[to1,to2,y,];
a[to1,to2,pos or y,]:=fro1; a[to1,to2,pos or y,]:=fro2;
a[to1,to2,pos or y,]:=y;
if bo[to1,to2,pos or y]= then
begin
bo[to1,to2,pos or y]:=;
inc(e); if e= then e:=;
f[e,]:=to1; f[e,]:=to2; f[e,]:=pos or y;
end;
end;
if a[fro1,fro2,pos,]+a[to1,to2,y,]<a[fro1,fro2,pos or y,] then
begin
a[fro1,fro2,pos or y,]:=a[fro1,fro2,pos,]+a[to1,to2,y,];
a[fro1,fro2,pos or y,]:=to1; a[fro1,fro2,pos or y,]:=to2;
a[fro1,fro2,pos or y,]:=pos;
if bo[fro1,fro2,pos or y]= then
begin
bo[fro1,fro2,pos or y]:=;
inc(e); if e= then e:=;
f[e,]:=fro1; f[e,]:=fro2; f[e,]:=pos or y;
end;
end;
exit;
end;
if pos and( shl(x-))= then
wh(x+,y or( shl(x-)));
wh(x+,y);
end;
begin
readln(n,m);
for i:= to n do
for j:= to m do
for k:= to do a[i,j,k,]:=maxlongint div ;
for i:= to n do
for j:= to m do
begin
read(map[i,j]);
if map[i,j]= then
begin
inc(e); inc(cnt); f[e,]:=i; f[e,]:=j; f[e,]:= shl(cnt-);
a[i,j,f[e,],]:=; bo[i,j,f[e,]]:=;
end else
begin
inc(e); f[e,]:=i; f[e,]:=j; f[e,]:=;
a[i,j,,]:=map[i,j]; bo[i,j,]:=;
end;
end;
a[,,( shl cnt)-,]:=maxlongint;
while s<>e do
begin
inc(s); if s= then s:=;
fro1:=f[s,]; fro2:=f[s,]; pos:=f[s,];
if(pos=( shl cnt)-)and(a[fro1,fro2,pos,]<a[ans1,ans2,pos,])
then begin ans1:=fro1; ans2:=fro2; end;
bo[fro1,fro2,pos]:=;
for i:= to do
if(fro1+fx[i]>=)and(fro1+fx[i]<=n)and(fro2+fy[i]>=)and(fro2+fy[i]<=m)
then begin
to1:=fro1+fx[i]; to2:=fro2+fy[i];
wh(,);
end;
end;
writeln(a[ans1,ans2,( shl cnt)-,]);
ss(ans1,ans2,( shl cnt)-);
for i:= to n do
begin
for j:= to m do
begin
if map[i,j]= then write('x')
else if map2[i,j]= then write('o')
else write('_');
end;
writeln;
end;
end.