https://www.luogu.com.cn/problem/P4294
斯坦纳树做什么？
一个图，其中有(k)个关键点，选一个生成树把这些关键点连起来，求最小的生成树边权和。
(k)通常比较小。
斯坦纳树怎么做？
记(f[i][S])为，现在有一棵以(i)为根的生成树，(Sin[0,2^k))表示连接了哪些关键点，的最小生成树边权和。
转移有两种：
1.枚举(t∈S),(f[i][S]=min(f[i][S],f[i][t]+f[i][S^t]-(i的点权(如果有的话))))
2.枚举(i)的相邻点(j),(f[i][S]=min(f[i][S],f[j][S]+(j->i的边权)+(i的点权)))
感性理解这样一定可以转移到每一棵生成树。
实现：
注意到第二个转移有环，所以需要最短路算法，如果把每个(f[i][S])都视作一个点，跑最短路，又不好处理第一个转移。
考虑分层图，以S分层，从小到大枚举S。
每一层开始前先做第一个转移，因为第一个转移一定是由低层转移来的。
接着第二个转移，第二个转移一定是在同一层之间转移，用最短路优化即可。
时间复杂度：
(O(n*3^k+2^k*(m+n)*log~m))
这题：
还需要给出方案，对每一个点记录它是由谁转移而来，倒退回去即可。
Code：
#include<bits/stdc++.h>
#define fo(i, x, y) for(int i = x, _b = y; i <= _b; i ++)
#define ff(i, x, y) for(int i = x, _b = y; i < _b; i ++)
#define fd(i, x, y) for(int i = x, _b = y; i >= _b; i --)
#define ll long long
#define pp printf
#define hh pp("
")
using namespace std;
const int N = 12;
int a2[N];
int n, m, a[N][N];
int id[N][N], id0;
void Init() {
a2[0] = 1; fo(i, 1, 10) a2[i] = a2[i - 1] * 2;
scanf("%d %d", &n, &m);
fo(i, 1, n) fo(j, 1, m) scanf("%d", &a[i][j]);
fo(i, 1, n) fo(j, 1, m) if(!a[i][j])
id[i][j] = ++ id0;
}
int mov[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
const int M = 1 << 10;
const int inf = 1e9;
struct P {
int x, y, v;
};
bool operator < (P a, P b) { return a.v > b.v;}
priority_queue<P> q;
int bz[N][N];
int f[N][N][M];
int fr[N][N][M][3];
void work() {
fo(i, 1, n) fo(j, 1, m) ff(s, 1, a2[id0]) f[i][j][s] = inf;
fo(i, 1, n) fo(j, 1, m) {
if(id[i][j]) f[i][j][a2[id[i][j] - 1]] = 0;
f[i][j][0] = a[i][j];
}
ff(s, 0, a2[id0]) {
fo(i, 1, n) fo(j, 1, m) {
for(int t = (s - 1) & s; t; t = (t - 1) & s) {
int v = f[i][j][t] + f[i][j][s ^ t] - a[i][j];
if(v < f[i][j][s]) {
f[i][j][s] = v;
fr[i][j][s][0] = i;
fr[i][j][s][1] = j;
fr[i][j][s][2] = t;
}
}
}
fo(i, 1, n) fo(j, 1, m) {
bz[i][j] = 0;
q.push((P) {i, j, f[i][j][s]});
}
while(q.size()) {
P b = q.top(); q.pop();
if(bz[b.x][b.y]) continue;
bz[b.x][b.y] = 1;
fo(k, 0, 3) {
int l = b.x + mov[k][0], r = b.y + mov[k][1];
if(l && r && l <= n && r <= m) {
ll v = b.v + a[l][r];
if(v < f[l][r][s]) {
f[l][r][s] = v;
q.push((P) {l, r, v});
fr[l][r][s][0] = b.x;
fr[l][r][s][1] = b.y;
fr[l][r][s][2] = s;
}
}
}
}
}
}
int cho[N][N];
void dg(int x, int y, int s) {
cho[x][y] = 1;
if(!fr[x][y][s][0]) return;
if(fr[x][y][s][2] == s) {
dg(fr[x][y][s][0], fr[x][y][s][1], s);
} else {
dg(x, y, fr[x][y][s][2]);
dg(x, y, s ^ fr[x][y][s][2]);
}
}
void End() {
int ans = inf, x, y;
fo(i, 1, n) fo(j, 1, m) {
ll v = f[i][j][a2[id0] - 1];
if(v < ans) {
ans = v;
x = i, y = j;
}
}
pp("%d
", ans);
dg(x, y, a2[id0] - 1);
fo(i, 1, n) {
fo(j, 1, m) {
if(!a[i][j]) pp("x"); else
pp("%c", cho[i][j] ? 'o' : '_');
}
hh;
}
}
int main() {
Init();
work();
End();
}