写的第一道斯坦纳树的题目。斯坦纳树在信息学中的应用一般为：在(n)个点之间给定(k)条边并相应的边权，求在保证给定(m)个点联通的条件下的最小边权和。解决此类问题的方法即为SPFA + 状压DP。参考论文：姜碧野 《SPFA的优化与应用》
我们用(dp[u][S])表示以u为根，联通状态为S（01状态）的最小权值。以u为根：最优解必然构成一棵最小生成树。那么有两种转移方式：
(dp[u][S] = dp[u][k'] + dp[u][k''] - a[u] left ( S = k' + k'' ight ))
这一个可以理解为(u)点为树上的一个分叉点，由该点分别走向两侧，一侧联通(k')集合，一侧联通(k'')集合，通过(u)点联通成(S)集合。这种转移比较好处理，只需枚举子集即可。
(dp[u][S] = dp[v][S] + w[u][v])
这里是从(u)点走向了(v)点，联通了这两个集合，通过(u -> v)这条边来连接。这一种情况就比较复杂了：(u)可以转移到(v)，(v)也可以转移到(u)，但这个方程式却给了我们一点联想：好像很像是最短路中的松弛操作呀。其满足三角形不等式，虽然图中有环的存在，但最优解并不构成环。所以我们用SPFA来进行这一部分的DP。
在本题中，(f[i][j][S])代表以点(i, j)为根，联通状态为(S)的最优权值。
#include <bits/stdc++.h> using namespace std; #define maxn 12 #define maxm (1 << 10) + 2 #define INF 1e9 int n, m, K, f[maxn][maxn][maxm]; int a[maxn][maxn], bin[maxn]; int dx[5] = {0, 0, 1, -1}, dy[5] = {1, -1, 0, 0}; bool vis[maxn][maxn]; struct node { int x, y; node (int _x = 0, int _y = 0) { x = _x, y = _y; } }; queue <node> q; struct Path { int x, y, s; Path (int _x = 0, int _y = 0, int _s = 0) { x = _x, y = _y, s = _s; } }path[maxn][maxn][maxm]; int read() { int x = 0, k = 1; char c; c = getchar(); while(c < '0' || c > '9') { if(c == '-') k = -1; c = getchar(); } while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * k; } void init() { bin[0] = 1; for(int i = 1; i < 20; i ++) bin[i] = bin[i - 1] << 1; } void SPFA(int S) { while(!q.empty()) { int x = q.front().x, y = q.front().y; vis[x][y] = 0, q.pop(); for(int k = 0; k < 4; k ++) { int X = x + dx[k], Y = y + dy[k]; if(X < 1 || Y < 1 || X > n || Y > m) continue; if(f[X][Y][S] > f[x][y][S] + a[X][Y]) { f[X][Y][S] = f[x][y][S] + a[X][Y]; path[X][Y][S] = Path(x, y, S); if(!vis[X][Y]) q.push(node(X, Y)), vis[X][Y] = 1; } } } } #define t path[x][y][S] void dfs(int x, int y, int S) { if(x > INF || !t.s) return; vis[x][y] = 1; dfs(t.x, t.y, t.s); if(t.x == x || t.y == y) dfs(x, y, S ^ t.s); } #undef t void Solve() { for(int S = 1; S < bin[K]; SPFA(S ++)) for(int i = 1; i <= n; i ++) for(int j = 1; j <= m; j ++) { for(int k = S & (S - 1); k; k = (k - 1) & S) { int t = f[i][j][k] + f[i][j][S ^ k] - a[i][j]; if(t < f[i][j][S]) { f[i][j][S] = t; path[i][j][S] = Path(i, j, k); } } if(f[i][j][S] != INF) { q.push(node(i, j)); vis[i][j] = 1; } } } void Get_ans() { for(int i = 1; i <= n; i ++) for(int j = 1; j <= m; j ++) if(!a[i][j]) { dfs(i, j, bin[K] - 1); printf("%d ", f[i][j][bin[K] - 1]); return; } } int main() { init(); n = read(), m = read(); for(int i = 1; i <= n; i ++) for(int j = 1; j <= m; j ++) { a[i][j] = read(); if(!a[i][j]) K ++; } for(int i = 1; i <= n; i ++) for(int j = 1; j <= m; j ++) for(int k = 0; k < bin[K]; k ++) f[i][j][k] = path[i][j][k].x = INF; K = 0; for(int i = 1; i <= n; i ++) for(int j = 1; j <= m; j ++) if(!a[i][j]) f[i][j][bin[K]] = 0, K ++; Solve(); memset(vis, 0, sizeof(vis)); Get_ans(); for(int i = 1; i <= n; i ++, putchar(' ')) for(int j = 1; j <= m; j ++) if(!a[i][j]) putchar('x'); else if(vis[i][j]) putchar('o'); else putchar('_'); return 0; }