树形DP 第一题

Sat, 01 Oct 2011 13:54:00 GMT

http://poj.org/problem?id=1947

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;
}

3 2011-10-01 21:54 发表评论

C++博客-积跬步，至千里

树形DP 第一题