Rebuilding Roads
题目链接
分类：dfs and similar trees dp
1.题意概述
给你一颗有
n
个节点构成是树，现在要你删去最少的边，使得剩下连通的点构成的树刚好有
p个节点。
2.解题思路
容易想到是一个树形dp，
dp[i][j]
表示以
i
节点为根节点，得到
j个节点的子树需要去掉的最少边数，那么转移方程为：考虑其儿子
k
选或者不选——最后取个最小值就行
如果不去掉
k的子树：
dp[s][i]=min(dp[s][j]+dp[k][i−j]),0≤j≤i
如果去掉
k
的子树：
dp[s][i]=dp[s][i] 1
3.AC代码
#define N 152
int f[N][N], sonA[N], sonB[N];
bool pa[N];
int n, p;
void init() {
memset(pa,
0,
sizeof pa);
memset(sonA,
0,
sizeof sonA);
memset(sonB,
0,
sizeof sonB);
}
void dfs(
int u) {
fill(f[u], f[u] + p +
1, INF);
f[u][
1] =
0;
int k = sonA[u];
while (k) {
dfs(k);
per(i,
1, p +
1) {
int tmp = f[u][i] +
1;
rep(j,
1, i)
tmp = min(tmp, f[k][i - j] + f[u][j]);
f[u][i] = tmp;
}
k = sonB[k];
}
}
int main() {
while (~
scanf(
"%d%d", &n, &p)) {
init();
rep(i,
1, n) {
int u, v;
scanf(
"%d%d", &u, &v);
pa[v] =
1;
sonB[v] = sonA[u];
sonA[u] = v;
}
int sta =
0;
rep(i,
1, n +
1)
if (!pa[i]) {
sta = i;
break;
}
dfs(sta);
int ans = f[sta][p];
rep(i,
1, n +
1) {
if (i != sta)
ans = min(ans, f[i][p] +
1);
}
printf(
"%d\n", ans);
}
return 0;
}
