【题解】重建道路

第一道自己切掉的树形DP,写个题解纪念一下……

一 题目

原题链接

描述

一场可怕的地震后,人们用N个牲口棚(1≤N≤150,编号1..N)重建了农夫John的牧场。由于人们没有时间建设多余的道路,所以现在从一个牲口棚到另一个牲口棚的道路是惟一的。因此,牧场运输系统可以被构建成一棵树。John想要知道另一次地震会造成多严重的破坏。有些道路一旦被毁坏,就会使一棵含有P(1≤P≤N)个牲口棚的子树和剩余的牲口棚分离,John想知道这些道路的最小数目。

输入

第1行:2个整数,N和P
第2..N行:每行2个整数I和J,表示节点I是节点J的父节点。

输出

单独一行,包含一旦被破坏将分离出恰含P个节点的子树的道路的最小数目。


二 题解

首先可以有这么一个想法:设 f[u][s] 表示在节点 u ,获得大小为 s 的子树所需要删除的边的个数。

考虑转移要做什么
考虑对于一个 s ,我们需要找到一种“空间”的分配方案。讲的形象一点,设 s(vi) 表示在子树 vi 内我们留下的节点个数,其中 vi 表示当前节点 u 的第 i 个子节点;再设 c(vi) 表示我们在子树 vi 中留下 s(vi) 个节点所删除的边的数量。那么现在我们要做的事情就是:对于全部 vi ,找到一种 s(vi) 的分配方式,使得 ∑s(vi) = s ,且 ∑c(vi) 最小,然后我们就可以令 f[u][s] = ∑c(vi),也就完成了状态的转移。

然后上面那句“对于全部 vi ,找到一种 s(vi) 的分配方式,使得 ∑s(vi) = s ,且 ∑c(vi) 最小”,你不觉得这是一个背包么?
然后这个时候你就会发现我们所设的 f[u][s] 这个状态实际上是不完全的。不考虑滚动数组,我们应该设 f[u][k][s] 表示考虑节点 u 的前 k 个子节点,取 s 个节点所需要的最小花费,这就是一个背包。

方程
那么可以写出一个转移:f[u][k][s] = min(f[u][k-1][s] + 1, f[u][k-1][s-sv] + f[v][kv][sv]),其中 kv 表示 v 的所有子节点数量,sv 表示在子树 v 上选取的点的数量。
上面那个方程很好理解:前面表示不从子树 v 选取节点,那么要删除 (u,v) 这条边,答案 +1 ;后面是在考虑子树 v 内选取的节点个数。

考虑滚动
然后上面那个方程它一点也不可爱,考虑滚动掉 k 这一维,方程变成 f[u][s] = min(f[u][s] + 1, f[u][s-sv] + f[v][sv]),但是在转移的顺序上还有点小问题。
我们发现 f[u][k][s] 总从 f[u][k-1][s] 或 f[u][k-1][s-sv] 的状态更新。也就是说,去掉 k 这一维,我们需要保证 f[u][s-sv] 比 f[u][sv] 后更新,这样 f[u][sv] 才是我们想要用来转移的“上层状态”。那么也就是倒序枚举 s 去更新。

于是我们只需要枚举 s,然后再枚举 sv,去转移就好了。

考虑答案的统计
上面那个状态里面, u 实际上是强制选择的,否则就缺少一个能把若干子树连接起来的“桥梁”。但是贪心的想,我们不一定非得强制选择某一个节点啊。那么答案应该对所有的 f[u][p] 取一个 min 。然后还有一个问题,就是在某一个非根节点的位置,我们想要取出这棵子树,还得把这个节点和它的父亲节点断掉,那么答案还得 +1,细节见代码。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;

const int CN = 160;

class fs{
public: int to,nxt; void init(int t,int n) {to=t;nxt=n;}
}E[CN * 2];
int hd[CN],ecnt = 0;
void add(int x,int y) {E[++ecnt].init(y,hd[x]);hd[x]=ecnt;}

int n,P,ans,sum[CN],f[CN][CN]; // sum[u] 表示子树 u 的大小
void dfs(int u,int p){
sum[u] = 1; f[u][1] = 0; // 初始时不考虑子树,因此 f[u][1] = 1
for(int k=hd[u];k;k=E[k].nxt){
int v = E[k].to;
if(v == p) continue;
dfs(v, u); // 求出子树的答案
sum[u] += sum[v]; // 累加大小

for(int s=sum[u]; s; s--){ // 考虑背包问题的更新方式,那么一定要每次都更新一下
f[u][s] += 1; // 实际上是 f[u][k][s] = f[u][k-1][s] + 1 ,滚动了 k 这一维
for(int sv=0;sv<=min(s-1, sum[v]);sv++) // s-1 为了强制选根
f[u][s] = min(f[u][s], f[u][s - sv] + f[v][sv]);
}
}
}

int main()
{
//freopen("p1272.in","r",stdin);

scanf("%d%d",&n,&P);
for(int i=1;i<n;i++){
int x,y; scanf("%d%d",&x,&y);
add(x,y); add(y,x);
}

memset(f,0x3f,sizeof(f));
dfs(1,0);
ans = f[1][P]; for(int i=2;i<=n;i++) ans = min(ans, f[i][P] + 1); // 加上与父亲之间的那条边
printf("%d", ans);

return 0;
}

$$ - - - - \mathcal{End} - - - - $$


评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×