一开始看是插头dp，后来发现还有一个叫斯坦纳树的东西
什么叫斯坦纳树，就是使给定点连通开销和最小的树（可以包含多余的点）
到这张平面图上，我们不难想到用dp来解决，设f[x,y,S]表示连通集合为S，树根为点(x,y)的最小开销
不难得到两个方程式
f[x,y,S]=min(f[x,y,s']+f[x,y,S-s']-a[x,y]) S'是S的一个子集，相当于合并两个数
f[x,y,S]=min(f[x',y',S]+a[x,y]) (x',y')与(x,y)相邻
由于景点很少，我们显然可以用状压dp，初始f[景点坐标，景点状态]=0
第一个方程转移大家都会，第二个方程转移是没有明确转移顺序，只要转移起点，因此我们用spfa转移
所以总的处理转移，我们穷举连通状况，然后先用第一个方程转移，然后再用第二个方程转移
1 const dx:array[1..4] of longint=(0,0,1,-1); 2 dy:array[1..4] of longint=(1,-1,0,0); 3 inf=1000000007; 4 type node=record 5 x,y,k:longint; 6 end; 7 8 var q:array[0..1000010] of node; 9 pre:array[0..11,0..11,0..1025] of node; 10 f:array[0..11,0..11,0..1025] of longint; 11 v:array[0..11,0..11] of boolean; 12 a:array[0..11,0..11] of longint; 13 t,h,r,k,i,j,s,n,m,x,y:longint; 14 15 function make(i,j,k:longint):node; 16 begin 17 make.x:=i; 18 make.y:=j; 19 make.k:=k; 20 end; 21 22 procedure spfa(k:longint); 23 var i,x,y,x0,y0:longint; 24 begin 25 while h<=r do 26 begin 27 x0:=q[h].x; y0:=q[h].y; 28 v[x0,y0]:=false; 29 for i:=1 to 4 do 30 begin 31 x:=x0+dx[i]; 32 y:=y0+dy[i]; 33 if (x<0) or (x>n) or (y<0) or (y>m) then continue; 34 if f[x,y,k]>f[x0,y0,k]+a[x,y] then 35 begin 36 f[x,y,k]:=f[x0,y0,k]+a[x,y]; 37 pre[x,y,k]:=make(x0,y0,k); 38 if not v[x,y] then 39 begin 40 v[x,y]:=true; 41 inc(r); 42 q[r].x:=x; q[r].y:=y; 43 end; 44 end; 45 end; 46 inc(h); 47 end; 48 end; 49 50 procedure dfs(x,y,k:longint); 51 var m:node; 52 begin 53 v[x,y]:=true; 54 m:=pre[x,y,k]; 55 if m.x=0 then exit; 56 dfs(m.x,m.y,m.k); 57 if (m.x=x) and (m.y=y) then dfs(m.x,m.y,k-m.k); 58 end; 59 60 begin 61 readln(n,m); 62 for i:=1 to n do 63 for j:=1 to m do 64 for k:=0 to 1024 do 65 f[i,j,k]:=inf; 66 for i:=1 to n do 67 for j:=1 to m do 68 begin 69 read(a[i,j]); 70 if a[i,j]=0 then 71 begin 72 f[i,j,1 shl t]:=0; 73 inc(t); 74 end; 75 end; 76 h:=1; 77 r:=0; 78 for k:=1 to 1 shl t-1 do 79 begin 80 for i:=1 to n do 81 for j:=1 to m do 82 begin 83 s:=k and (k-1); 84 while s<>0 do //穷举子集 85 begin 86 if f[i,j,k]>f[i,j,s]+f[i,j,k-s]-a[i,j] then 87 begin 88 f[i,j,k]:=f[i,j,s]+f[i,j,k-s]-a[i,j]; 89 pre[i,j,k]:=make(i,j,s); //记录从哪转移来的 90 end; 91 s:=k and (s-1); 92 end; 93 if f[i,j,k]<inf then 94 begin 95 v[i,j]:=true; 96 inc(r); 97 q[r].x:=i; q[r].y:=j; 98 end; 99 end; 100 spfa(k); 101 h:=1; 102 r:=0; 103 end; 104 for i:=1 to n do 105 for j:=1 to m do 106 if a[i,j]=0 then 107 begin 108 x:=i; 109 y:=j; 110 break; 111 end; 112 113 writeln(f[x,y,1 shl t-1]); 114 dfs(x,y,1 shl t-1); 115 for i:=1 to n do 116 begin 117 for j:=1 to m do 118 if a[i,j]=0 then write('x') 119 else if v[i,j] then write('o') 120 else write('_'); 121 writeln; 122 end; 123 end.