题解 P4294 【[WC2008]游览计划】
RabbitHu
2018-03-20 17:22:23
## 题解
这道题是【斯坦纳树】的经典例题。斯坦纳树是这样一类问题：带边权无向图上有几个（一般约10个）点是【关键点】，要求选择一些边使这些点在同一个联通块内，同时要求所选的边的边权和最小。
怎么解决斯坦纳树问题？……其实，就是一种状压DP。
$dp[i][j]$表示以i号节点为根，当前状态为j（j的二进制中已经与i连通的点对应位置为1）。
这个“以i为根”是哪来的呢？其实i可以是联通块中任意一个点，没有额外限制，只是引入这个i就可以DP了。
当根i不改变时（即合并两个都包含i的联通块）状态转移方程是：
$$dp[i][j] = \min_{s \in j}\{dp[i][s] + dp[i][\complement_js] - val[i]\}$$
（$val[i]$表示本题中i号点的权值，减去一个是因为$dp[i][s]$和$dp[i][\complement_js]$中都含有i号点的权值，要防止“加重了”）
当根改变时（即在原有联通块中加入一个新节点i并设置为根，要求i、k相邻）：
$$dp[i][j] = \min\{dp[k][j] + val[i]\}$$
第一个状态转移方程有顺序，可以直接DP；而第二个状态转移方程没有明显顺序，但可以按照最短路的SPFA算法“DP”（神奇！）。
## 代码
```cpp
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <queue>
#define space putchar(' ')
#define enter putchar('\n')
using namespace std;
typedef long long ll;
template <class T>
void read(T &x){
char c;
bool op = 0;
while(c = getchar(), c < '0' || c > '9')
if(c == '-') op = 1;
x = c - '0';
while(c = getchar(), c >= '0' && c <= '9')
x = x * 10 + c - '0';
if(op) x = -x;
}
template <class T>
void write(T x){
if(x < 0) putchar('-'), x = -x;
if(x >= 10) write(x / 10);
putchar('0' + x % 10);
}
const int INF = 0x3f3f3f3f;
int n, m, K, root, f[101][1111], a[101], ans[11][11];
bool inq[101];
typedef pair<int, int> par;
typedef pair<par, int> rec;
#define fi first
#define se second
#define mp make_pair
#define num(u) (u.fi * m + u.se)
rec pre[101][1111];
const int dx[] = {0, 0, -1, 1};
const int dy[] = {1, -1, 0, 0};
queue<par> que;
bool legal(par u){
return u.fi >= 0 && u.se >= 0 && u.fi < n && u.se < m;
}
void spfa(int now){
while(!que.empty()){
par u = que.front();
que.pop();
inq[num(u)] = 0;
for(int d = 0; d < 4; d++){
par v = mp(u.fi + dx[d], u.se + dy[d]);
int nu = num(u), nv = num(v);
if(legal(v) && f[nv][now] > f[nu][now] + a[nv]){
f[nv][now] = f[nu][now] + a[nv];
if(!inq[nv]) inq[nv] = 1, que.push(v);
pre[nv][now] = mp(u, now);
}
}
}
}
void dfs(par u, int now){
if(!pre[num(u)][now].se) return;
ans[u.fi][u.se] = 1;
int nu = num(u);
if(pre[nu][now].fi == u) dfs(u, now ^ pre[nu][now].se);
dfs(pre[nu][now].fi, pre[nu][now].se);
}
int main(){
read(n), read(m);
memset(f, 0x3f, sizeof(f));
for(int i = 0, tot = 0; i < n; i++)
for(int j = 0; j < m; j++){
read(a[tot]);
if(!a[tot]) f[tot][1 << (K++)] = 0, root = tot;
tot++;
}
for(int now = 1; now < (1 << K); now++){
for(int i = 0; i < n * m; i++){
for(int s = now & (now - 1); s; s = now & (s - 1))
if(f[i][now] > f[i][s] + f[i][now ^ s] - a[i]){
f[i][now] = f[i][s] + f[i][now ^ s] - a[i];
pre[i][now] = mp(mp(i / m, i % m), s);
}
if(f[i][now] < INF)
que.push(mp(i / m, i % m)), inq[i] = 1;
}
spfa(now);
}
write(f[root][(1 << K) - 1]), enter;
dfs(mp(root / m, root % m), (1 << K) - 1);
for(int i = 0, tot = 0; i < n; i++){
for(int j = 0; j < m; j++)
if(!a[tot++]) putchar('x');
else putchar(ans[i][j] ? 'o' : '_');
enter;
}
return 0;
}
```