重建道路
题目链接
This is -single$hot
题目
一场可怕的地震后,人们用 N 个牲口棚(编号 1∼N)重建了农夫 John 的牧场。由于人们没有时间建设多余的道路,所以现在从一个牲口棚到另一个牲口棚的道路是惟一的。因此,牧场运输系统可以被构建成一棵树。
John 想要知道另一次地震会造成多严重的破坏。有些道路一旦被毁坏,就会使一棵含有 P 个牲口棚的子树和剩余的牲口棚分离,John 想知道这些道路的最小数目。
分析
这是一个典型的树上背包问题
类似一个多重背包,这个一般是树形DP的难题。
题解已经很清晰了,下面是代码 :
#include <bits/stdc++.h>
using namespace std;
const int N = 310;
inline int read(int s = 0, int f = 1, char ch = getchar()) {
while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar(); }
while(isdigit(ch)) { s = s*10 + ch - '0'; ch = getchar(); }
return s * f;
}
int n, p, chu[N], in[N], f[N][N], head[N], cnt, root, ans;
struct edge { int to, next; } e[N<<1];
inline void add(int x, int y) { e[++cnt].to = y, e[cnt].next = head[x], head[x] = cnt; }
int dfs(int u) {
int temp, sum = 1;
for(int i = head[u], v; i; i = e[i].next) {
v = e[i].to, temp = dfs(v), sum += temp;
for(int j = sum; j >= 1; j--)
for(int k = 1; k < j; ++k)
f[u][j] = min(f[u][j], f[u][j - k] + f[v][k] - 1);
}
return sum;
}
int main() {
n = read(), p = read();
for(int i = 1, x, y; i <= n-1; ++i)
x = read(), y = read(), chu[x]++, in[y]++, add(x, y);
memset(f, 0x3f, sizeof(f));
for(int i = 1; i <= n; ++i) {
if(in[i] == 0) root = i;
f[i][1] = chu[i];
}
dfs(root);
ans = f[root][p];
for(int i = 1; i <= n; ++i) ans = min(ans, f[i][p] + 1);
return cout << ans, 0;
}