题目大意：给定一个网格图，有些点是关键点，选择格点有代价，求把所有关键点联通的最小代价
斯坦纳树模板题
斯坦纳树问题：给定一个图结构，有一些点是关键点，求把这些关键点联通的最小代价e
斯坦纳树问题其实是最小生成树MST问题的扩展
考虑状压DP，设f[x][s]代表当前以x为根的树，关键点选取状态集合为s时的最小代价
考虑s由两个子集s1和s2转移过来，则DP方程为f[x][s]=f[x][s1]+f[x][s2]。如果是点权，去重还要减去val[x]。
考虑s由其它点转移过来，那么就枚举其它点，f[x][s]=f[y][s]+val[x][y]，发现这其实就是最短路的转移形式，我们一开始把所有f<inf的点扔队列里跑spfa就行了
初始化：对于关键点x，有f[x][只包含x的集合]=0，其它为inf
最后输出的答案即为f[某个关键点][(1<<tot)-1]
瞎写的板子：
for (int s = 1; s < (1 << tot); s++)
{
for (int i = 1; i <= n; i++)
{
for (s1 + s2 == s)
{
chkmin(f[i][s], f[i][s1]+f[i][s2]);
if (f[i][s] < inf) q.push(i), vis[i] = true;
}
}
while (!q.empty())
{
int x = q.front(); q.pop(), vis[x] = false;
for (int i : out[x]) if (f[x][s] + dis[x][i] < f[i][s])
{
f[i][s] = f[x][s] + dis[x][i];
if (vis[i] == false) vis[i] = true, q.push(i);
}
}
}
本题题解：
直接套用板子即可。
由于还要输出方案，我们维护一个pre，记录这个状态从哪个状态转移过来的，dfs一遍就行了。
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
struct data { int x, y, s; } pre[15][15][1050];
int n, m, tot, mp[15][15], f[15][15][1050], ex, ey;
bool vis[15][15], ans[15][15];
void dfs(int x, int y, int s)
{
if (pre[x][y][s].s == 0) return;
ans[x][y] = true;
dfs(pre[x][y][s].x, pre[x][y][s].y, pre[x][y][s].s);
if (pre[x][y][s].x == x && pre[x][y][s].y == y) dfs(pre[x][y][s].x, pre[x][y][s].y, pre[x][y][s].s ^ s);
}
int main()
{
scanf("%d%d", &n, &m); memset(f, 0x3f, sizeof(f));
for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++)
{
scanf("%d", &mp[i][j]);
if (mp[i][j] == 0) f[i][j][1 << (tot++)] = 0, ex = i, ey = j;
}
for (int s = 1; s < (1 << tot); s++)
{
queue<int> qx, qy;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
for (int s1 = s; s1 > 0; s1 = (s1 - 1) & s)
{
int s2 = s1 ^ s;
if (f[i][j][s] > f[i][j][s1] + f[i][j][s2] - mp[i][j])
{
f[i][j][s] = f[i][j][s1] + f[i][j][s2] - mp[i][j];
pre[i][j][s] = (data){i, j, s1};
}
}
if (vis[i][j] == false && f[i][j][s] != 0x3f3f3f3f) qx.push(i), qy.push(j), vis[i][j] = true;
}
}
while (!qx.empty())
{
int x = qx.front(), y = qy.front(); qx.pop(), qy.pop(); vis[x][y] = false;
for (int d = 0; d < 4; d++)
{
int nx = x + dx[d], ny = y + dy[d];
if (nx >= 1 && nx <= n && ny >= 1 && ny <= m)
{
if (f[nx][ny][s] > f[x][y][s] + mp[nx][ny])
{
f[nx][ny][s] = f[x][y][s] + mp[nx][ny];
pre[nx][ny][s] = (data){x, y, s};
if (vis[nx][ny] == false) vis[nx][ny] = true, qx.push(nx), qy.push(ny);
}
}
}
}
}
printf("%d
", f[ex][ey][(1 << tot) - 1]);
dfs(ex, ey, (1 << tot) - 1);
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
if (mp[i][j] == 0) printf("x");
else if (ans[i][j]) printf("o");
else printf("_");
printf("
");
}
return 0;
}