题目
点击查看题目
题目描述
一场可怕的地震后，人们用 \(N\) 个牲口棚（编号 \(1\sim N\)）重建了农夫 John 的牧场。由于人们没有时间建设多余的道路，所以现在从一个牲口棚到另一个牲口棚的道路是唯一的。因此，牧场运输系统可以被构建成一棵树。
John 想要知道另一次地震会造成多严重的破坏。有些道路一旦被毁坏，就会使一棵含有 \(P\) 个牲口棚的子树和剩余的牲口棚分离，John 想知道这些道路的最小数目。
限制与约定
\(1\le N\le 150\)，\(1\le P\le N\)，保证给出的是一棵树。
思路
设 \(f_{i, j}\) 表示以点 \(i\) 为子树，保留 \(j\) 个结点需要删除的边的最小值。
初始状态：\(f_{i, 1} = 与结点 i 相连的点的个树\)，即只保留一个点，就需要把所有子结点割掉。
状态转移：\(f_{u, j} = \min(f_{u, j}, f_{u, j - k} + f_{to, k} - 1)\)，因为要保留以 \(to\) 为子树的一些结点，所以撤销删除 \(u\) 到 \(to\) 的那条边。注意和 01 背包一样要倒序枚举。
答案：对于根结点 1，答案为 \(f_{1, p}\)；对于其他结点 \(u\)：答案为 \(f_{u, p} + 1\)，因为要断掉它和父结点的关系，要多删一条边。
代码
细节巨多。
#include <bits/stdc++.h>
using namespace std;
const int N = 210;
int n, p;
vector<int> e[N];
int f[N][N], sz[N];
void dfs(int u) {
f[u][1] = e[u].size();
sz[u] = 1;
for (auto to : e[u]) {
dfs(to);
sz[u] += sz[to];
for (int j = sz[u]; j >= 1; j--) {// j 只能到 1
for (int k = 1; k <= min(sz[to], j - 1); k++) {// k 要从 1 开始
f[u][j] = min(f[u][j], f[u][j - k] + f[to][k] - 1);// 注意：-1
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> p;
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
e[u].push_back(v);
}
memset(f, 0x3f, sizeof(f));
dfs(1);
int ans = f[1][p];// 特殊处理根结点
for (int i = 2; i <= n; i++) ans = min(ans, f[i][p] + 1);// 其他结点要 +1！
cout << ans << '\n';
return 0;
}