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 閱讀(2283)
評論(2) 編輯 收藏 引用 所屬分類:
poj