poj 1947 Rebuilding Roads

本文从WordPress迁移而来, 查看全部WordPress迁移文章

树dp 背包

题意:用最少的切割次数,分割出一个节点数为p的子树

由于我们不知道最后得到的是哪个子树,所有可以全部求出来,最后枚举每个点,以该点作为根的子树下有p个节点的切割次数是多少
定义:dp[u][m]:表示以u为根的子树下有m个节点的最小切割次数,注意这里,u和它的父亲fa的连边是没有切断的,但是我们并不考虑它的fa分支,只看u这个子树,所以最后要使的u这个子树完全独立出来,还要切割多一次,切断u和fa的连线

最终的答案是

ans = dp[1][p];以1为根的子树下有p个节点的最少切割次数,由于1没有fa,所以不用加1

ans = min{ dp[u][p] } + 1 ; 以其他点为根的子树下有p个节点的最少切割次数,但是其他节点u都有fa,所以还要切掉u和fa的边

dp的转移:我们先来考虑这个问题。u为根的子树有m个节点,u有儿子v1,v2,v3,…….假设v1子树有k1个节点,v2子树有k2的节点,v3子树有k3个节点………….这其实就是一个组合起来的结果

dp[u][m] = dp[v1][k1] + dp[v2][k2] + dp[v3][k3] + dp[v4][k4]………………….

但每个子树下面保留多少个节点,是不确定的,可以1个,0个,多个。这其实就转化为了背包

总容量为m,每个子树下应该选进去多少个点ki,使得不超过容量m,价值最小

转移方程为

dp[u][j] = min(dp[u][j],dp[u][j-k] + dp[v][k] - 1);

有时候写dp[u][j]会不好理解,实际上是dp[u][c][j]的,只不过和背包一样,进行了空间的优化,降维

dp[u][c][j]表示以u为根的子树,在考虑第前c个儿子子树后,包含了j个节点的最少切割次数,这和dp[u][j]是一样的

dp[u][1] = son; 以u为根的子树只保留一个节点u,那么说明其儿子都切断了,有多少个儿子子树只需要切多少刀,因而切son次

关于转移方程 dp[u][j] = min(dp[u][j],dp[u][j-k] + dp[v][k] - 1);

dp[u][j-k] + dp[v][k] - 1 , dp[u][j-k]表示前c个儿子一共贡献了j-k个节点给u这个子树,dp[v][k]表示第c+1个儿子贡献了k个节点给u,为何要减1,因为对于u而言,相当于v子树拼接到u上次,要抵消掉之前切去的那条u—v的边

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
49
50
51
52
53
54
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
#define N 200
#define INF 0x3f3f3f3f
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))
#define pb push_back

int n,p;
vector<int>e[N];
int dp[N][N];

void dfs(int u,int fa){
int son = 0;
for(int i = 0; i < e[u].size(); i++){
int v = e[u][i];
if(v == fa) continue;
dfs(v,u);
son++;
}
dp[u][1] = son;
for(int i = 0; i < e[u].size(); i++){
int v = e[u][i];
if(v == fa) continue;
for(int j = p; j >= 2; j--)
for(int k = 1; k < j; k++)
if(dp[u][j-k] != INF && dp[v][k] != INF){
dp[u][j] = min(dp[u][j],dp[u][j-k] + dp[v][k] - 1);
}
}
}

int main(){
while(scanf("%d%d",&n,&p)!=EOF){
for(int i = 1; i <= n; i++)
e[i].clear();
for(int i = 1; i < n; i++){
int u,v;
scanf("%d%d",&u,&v);
e[u].pb(v); e[v].pb(u);
}
cl(dp,0x3f);
dfs(1,-1);
int ans = INF;
for(int i = 1; i <= n; i++){
if(i == 1) ans = min(ans,dp[i][p]);
else ans = min(ans,dp[i][p]+1);
}
printf("%d\n",ans);
}
return 0;
}