wc！！！斯坦納樹！！！！！！！！！！！！！！！！！！！！
while (1) {iq--，膝蓋++；}
還是不太了解的樣子。。。。（過幾天自己就會了，，不虛（大霧））
1 #include<cstdio>
2 #include<iostream>
3 #include<algorithm>
4 #include<map>
5 #include<queue>
6 #define N 1000005
7 #define inf 1000000000
8 #define LL long long
9 using namespace std;
10 int a[15][15];
11 int bin[20];
12 int n,m,K;
13 int f[12][12][1024];
14 struct data{
15 int fir,sed,thd;
16 }pre[15][15][1024];
17 int xx[4]={0,0,1,-1},yy[4]={1,-1,0,0};
18 queue<pair<int , int > >q;
19 bool inq[15][15],vis[15][15];
20 void spfa(int st)
21 {
22 while (!q.empty())
23 {
24 int x=q.front().first,y=q.front().second;
25 inq[x][y]=0; q.pop();
26 for (int k=0; k<4; k++)
27 {
28 int nowx=x+xx[k],nowy=y+yy[k];
29 if (nowx<1 || nowy<1 || nowx>n || nowy>m) continue;
30 if (f[nowx][nowy][st]>f[x][y][st]+a[nowx][nowy])
31 {
32 f[nowx][nowy][st]=f[x][y][st]+a[nowx][nowy];
33 pre[nowx][nowy][st]=(data){x,y,st};
34 if (!inq[nowx][nowy])
35 {
36 q.push(make_pair(nowx,nowy));
37 inq[nowx][nowy]=1;
38 }
39 }
40 }
41 }
42 }
43 void dfs(int x, int y, int st)
44 {
45 if (x>inf || pre[x][y][st].thd==0) return;
46 vis[x][y]=1;
47 data t=pre[x][y][st];
48 dfs(t.fir,t.sed,t.thd);
49 if (t.fir==x && t.sed==y) dfs(x,y,st-t.thd);
50 }
51 int main()
52 {
53 bin[0]=1; for (int i=1; i<20; i++) bin[i]=bin[i-1]<<1;
54 scanf("%d%d",&n,&m);
55 for (int i=1; i<=n; i++)
56 for (int j=1; j<=m; j++)
57 {
58 scanf("%d",&a[i][j]);
59 if (!a[i][j]) K++;
60 }
61 for (int i=1; i<=n; i++)
62 for (int j=1; j<=m; j++)
63 for (int k=0; k<bin[K]; k++)
64 f[i][j][k]=pre[i][j][k].fir=inf;
65 K=0;
66 for (int i=1; i<=n; i++)
67 for (int j=1; j<=m; j++)
68 if (!a[i][j]) f[i][j][bin[K++]]=0;
69 for (int st=1; st<bin[K]; st++)
70 {
71 for (int i=1; i<=n; i++)
72 for (int j=1; j<=m; j++)
73 {
74 for (int s=st&(st-1);s;s=st&(s-1))
75 {
76 int t=f[i][j][s]+f[i][j][st-s]-a[i][j]; //?????
77 if (t<f[i][j][st])
78 {
79 printf("%d %d %d",i,j,s); while (1);
80 f[i][j][st]=t;
81 pre[i][j][st]=(data){i,j,s};
82 }
83 }
84 if (f[i][j][st]<inf) q.push(make_pair(i,j)),inq[i][j]=1;
85 }
86 spfa(st);
87 }
88 int x,y;
89 for (int i=1; i<=n; i++)
90 for (int j=1; j<=m; j++)
91 if (!a[i][j])
92 {
93 x=i; y=j; break;
94 }
95 dfs(x,y,bin[K]-1);
96 printf("%d
",f[x][y][bin[K]-1]);
97 for (int i=1; i<=n; i++)
98 {
99 for (int j=1; j<=m; j++)
100 {
101 if (!a[i][j]) printf("x");
102 else if (vis[i][j]) printf("o");
103 else printf("_");
104 }
105 puts("");
106 }
107 return 0;
108 }