[POI2014] TUR-Tourism
题意
给出一张图，在这张图中，任意两点间不存在节点数超过 \(10\) 的简单路径。
第 \(i\) 个点被选的代价为 \(C_i\)，每个节点要么选，要么与它直接相连的点中至少有一个被选。
求最小代价。
思路
图的生成树上状压动态规划。
由于给出的是一张图，无法直接dp，我们可以在这张图的 dfs 树上dp。
又因为任意两点间不存在节点数超过 \(10\) 的简单路径，
我们可以把每个点到根的路径上点的状态进行压缩。
\(0\)：这个点选了。
\(1\)：这个点没选也没被覆盖。
\(2\)：这个点没选但被覆盖。
每次从子节点回收答案，看子节点选还是不选被覆盖。
每次还需要从父节点继承答案，枚举返祖边。
通过祖先的状态，统计出当前点选和不选时的状态，从父亲的 dp 值继承过来。
实现时用 \(dp_{i,j}\) 表示深度为 \(i\)（而不是点 \(i\)），状态为 \(j\) 的最小值，每次清空节省空间。
代码和注释
#define Get(x, y) ((x) / Pow[y] % 3)
#define Set(x, y, v) (x -= Get(x, y) * Pow[y], x += v * Pow[y])
#define min(x, y) ((x) < (y) ? (x) : (y))
const int N = 1e5 + 5;
/*
0:选了
1:不选且未被覆盖
2:不选且被覆盖
*/
int ver[N << 1], nxt[N << 1], head[N];
int a[N], n, m, tot;
int dep[N], ans, cnt, z[N];
int dp[11][N], Pow[11];
bool vis[N];
void add(int x, int y) {
ver[++ tot] = y;
nxt[tot] = head[x];
head[x] = tot;
}
void dfs(int x) {
vis[x] = 1, cnt = 0;
for (int i = head[x], y; i; i = nxt[i]) {
y = ver[i];
if (vis[y]) z[++ cnt] = dep[y]; // 返祖边连向的祖先
}
if (dep[x] == 0) { // 根节点
dp[0][0] = a[x];
dp[0][1] = 0;
dp[0][2] = 1e9;
} else {
for (int i = 0; i < Pow[dep[x] + 1]; i ++) dp[dep[x]][i] = 1e9; // 赋值
for (int i = 0; i < Pow[dep[x]]; i ++) { // 枚举父亲状态
int yes = i, no = i;
// yes:当前点选后的状态
// no:当前点不选后的状态
Set(no, dep[x], 1); // 初始时就是不选未覆盖
for (int j = 1; j <= cnt; j ++) {
int y = z[j];
if (Get(i, y) == 0) Set(no, dep[x], 2); // 如果有祖先选了,当前点变为未选被覆盖
if (Get(i, y) == 1) Set(yes, y, 2); // 如果有祖先不选未覆盖,把它变为未选被覆盖
}
dp[dep[x]][no] = min(dp[dep[x]][no], dp[dep[x] - 1][i]); // 没选当前点,直接继承
dp[dep[x]][yes] = min(dp[dep[x]][yes], dp[dep[x] - 1][i] + a[x]); // 选了当前点,加上权值
}
}
for (int i = head[x], y; i; i = nxt[i]) {
y = ver[i];
if (vis[y]) continue;
dep[y] = dep[x] + 1;
dfs(y);
for (int i = 0; i < Pow[dep[y]]; i ++)
dp[dep[x]][i] = min(/*选*/dp[dep[y]][i], /*不选被覆盖*/dp[dep[y]][i + 2 * Pow[dep[y]]]); // 从儿子回收答案
}
}
int main() {
memset(dp, 0x3f, sizeof(dp));
Pow[0] = 1;
for (int i = 1; i <= 10; i ++)
Pow[i] = Pow[i - 1] * 3;
read(n), read(m);
for (int i = 1; i <= n; i ++) read(a[i]);
for (int i = 1, u, v; i <= m; i ++) {
read(u), read(v);
add(u, v);
add(v, u);
}
for (int i = 1; i <= n; i ++) {
if (vis[i]) continue;
dfs(i);
ans += min(dp[0][0], dp[0][2]);
}
print(ans);
print_final();
return 0;
}