相当于对一个带有点权的图求使指定点集的连通的最小点权生成树
两种转移对于点权的处理： 1.dp[i][st[i] | state] = dp[j][state] + val[i]，即拓展了一个点 i，要加上点 i 的点权 2.dp[i][state] = dp[i][st] + dp[i][state ^ st] - val[i]，因为两棵子树都有val[i]，要扣掉重复的部分
对于这题还需要记录路径，记录路径的方法为每次更新的时候记录这个状态的前驱
子集dp更新部分：
if(dp[i][j] == -1 || dp[i][x] + dp[i][y] - a[i / m][i % m] < dp[i][j]) { dp[i][j] = dp[i][x] + dp[i][y] - a[i / m][i % m]; pre[i][j] = node(i,x); }spfa 更新部分：
if(dp[v][st[v] | state] == -1 || dp[v][st[v] | state] > dp[top][state] + a[v / m][v % m]) { dp[v][st[v] | state] = dp[top][state] + a[v / m][v % m]; pre[v][st[v] | state] = node(top,state); if((st[v] | state) != state || vis[v][state]) continue; q.push(v); vis[v][state] = 1; }对路径的搜索，用 dfs：
void dfs(int p,int s) { if(!pre[p][s].s) return; ans[p / m][p % m] = 1; dfs(pre[p][s].p,pre[p][s].s); if(pre[p][s].p == p) dfs(pre[p][s].p,(s ^ pre[p][s].s) | st[pre[p][s].p]); }即最终状态的树，一定由两棵子树转移得到，每次对子树 dfs,将子树的根节点标记。 如果当前状态是由子集dp更新得来，那么转移得到它的子树是两棵根节点仍未 x 的子树，分别对这两棵子树进行遍历即可。
代码：
#include<bits/stdc++.h> using namespace std; #define pii pair<int,int> #define fir first #define sec second typedef long long ll; const int maxn = 2e2 + 10; vector<int> g[maxn]; queue<int> q; const int inf = 0x3f3f3f3f; int dp[maxn * 10][1 << 10 + 1],a[maxn][maxn],st[maxn],sta[maxn],cnt,endst,tot; int vis[maxn][1 << 10 + 1],n,m;; int ans[maxn][maxn]; char tt[maxn][maxn]; int mx[4] = {1,0,-1,0}; int my[4] = {0,1,0,-1}; struct node{ int p,s; node(int pi = 0,int si = 0) { p = pi; s = si; } }pre[maxn][1 << 10 + 1]; void spfa(int state) { while(!q.empty()) { int top = q.front(); q.pop(); vis[top][state] = 0; for(auto it : g[top]) { int v = it; if(dp[v][st[v] | state] == -1 || dp[v][st[v] | state] > dp[top][state] + a[v / m][v % m]) { dp[v][st[v] | state] = dp[top][state] + a[v / m][v % m]; pre[v][st[v] | state] = node(top,state); if((st[v] | state) != state || vis[v][state]) continue; q.push(v); vis[v][state] = 1; } } } } void steniertree() { for(int i = 0; i < tot; i++) dp[i][st[i]] = 0; for(int j = 1; j < endst; j++) { for(int i = 0; i < tot; i++) { if(st[i] && (st[i] & j) == 0) continue; for(int k = j & (j - 1); k; k = (k - 1) & j) { int x = st[i] | k,y = st[i] | (j - k); if(dp[i][x] != -1 && dp[i][y] != -1) { if(dp[i][j] == -1 || dp[i][x] + dp[i][y] - a[i / m][i % m] < dp[i][j]) { dp[i][j] = dp[i][x] + dp[i][y] - a[i / m][i % m]; pre[i][j] = node(i,x); } } } if(dp[i][j] != -1) { q.push(i); vis[i][j] = 1; } } spfa(j); } } void dfs(int p,int s) { if(!pre[p][s].s) return; ans[p / m][p % m] = 1; dfs(pre[p][s].p,pre[p][s].s); if(pre[p][s].p == p) dfs(pre[p][s].p,(s ^ pre[p][s].s) | st[pre[p][s].p]); } int main() { scanf("%d%d",&n,&m); tot = n * m; int tx,ty; for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) { int p = i * m + j; scanf("%d",&a[i][j]); if(!a[i][j]) sta[++cnt] = p,tx = i,ty = j; } for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { for(int k = 0; k < 4; k++) { int x = i + mx[k],y = j + my[k]; if(x >= n || x < 0 || y >= m || y < 0) continue; int p = i * m + j,q = x * m + y; g[p].push_back(q); } } } endst = (1 << cnt); memset(dp,-1,sizeof dp); memset(st,0,sizeof st); for(int i = 1; i <= cnt; i++) st[sta[i]] = 1 << (i - 1); steniertree(); int res = dp[sta[1]][endst - 1]; dfs(sta[1],endst - 1); printf("%d\n",res); for(int i = 0; i < n * m; i++) { int x = i / m,y = i % m; tt[x][y] = '_'; if(a[x][y] == 0) tt[x][y] = 'x'; else if(ans[x][y] == 1) tt[x][y] = 'o'; } for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) printf("%c",tt[i][j]); puts(""); } return 0; }