dp[s][i]:记录s结点，要得到一棵j个节点的子树去掉的最少边数
考虑其儿子k
1）如果不去掉k子树，则
dp[s][i] = min(dp[s][j]+dp[k][i-j]) 0 <= j <= i
2）如果去掉k子树，则
dp[s][i] = dp[s][i]+1
总的为
dp[s][i] = min (min(dp[s][j]+dp[k][i-j]) , dp[s][i]+1 )
#include <iostream>
#define MAX 152
#define INF 0x3ffffff
using namespace std;
/**//*
dp[s][i]:记录s结点，要得到一棵j个节点的子树去掉的最少边数
考虑其儿子k
1）如果不去掉k子树，则
dp[s][i] = min(dp[s][j]+dp[k][i-j]) 0 <= j <= i
2）如果去掉k子树，则
dp[s][i] = dp[s][i]+1
总的为
dp[s][i] = min (min(dp[s][j]+dp[k][i-j]) , dp[s][i]+1 )
*/
int dp[MAX][MAX];
int son[MAX], bla[MAX], root, n, p;
//son[i]:记录i结点的儿子，bla[i]:记录i结点的兄弟
bool hf[MAX];
//hf[i]:i结点是否有父亲
void dfs(int s)
{
int i, j, k, temp;
for(i = 0; i <= p; i++)
dp[s][i] = INF;
dp[s][1] = 0;
k = son[s];
while(k){
dfs(k);
for(i = p; i >= 0; i--){
temp = dp[s][i]+1;
for(j = 0; j <= i; j++){
if(dp[k][i-j] + dp[s][j] < temp)
temp = dp[k][i-j] + dp[s][j];
}
dp[s][i] = temp;
}
k = bla[k];
}
}
int slove(int root)
{
dfs(root);
int i, ans;
ans = dp[root][p];
for(i = 1; i <= n; i++){
if(dp[i][p] < ans)
ans = dp[i][p] + 1;
}
return ans;
}
int main()
{
//freopen("data.txt", "r", stdin);
int i, s, t;
while(cin >> n >> p){
memset(son, 0, sizeof(son));
for(i = 1; i < n; i++){
cin >> s >> t;
bla[t] = son[s];
son[s] = t;
hf[t] = true;
}
for(i = 1; i <= n; i++){
if(!hf[i])
root = i;
}
cout << slove(root) << endl;
}
return 0;
}posted on 2009-05-15 11:37
longshen 阅读(2253)
评论(2) 编辑 收藏 引用 所属分类:
poj