poj 1947 Rebuilding Roads (樹形背包dp)

本文出自   http://blog.csdn.net/shuangde800

題目連結:  poj-1947

題意

    給一棵樹,問最少删掉幾條邊.使得剩下的子樹中有節點個數為p個的

思路

    幾天前就看了這題, 但是沒什麼想法,之後每天都有去想一下, 直到今天, 在我對自己方法還有懷疑

    的情況下,竟然AC了..

    f(i, j) 表示子樹i,保留j個節點的最少删邊次數, 注意,這裡保留的j個節點的子樹,是指根節點

    為i的且有j個節點的子樹.這樣了解的話, 狀态轉移就容易想多了.

    對于子樹i, 如果隻保留1個節點,那麼連接配接它所有兒子節點的邊都要删掉,

    是以可以初始化 f(i, 1) = 節點i的兒子個數

    f(i, j), 即子樹i保留j個節點, 那麼對于i的每個子樹,可以選擇保留1,2,..j-1個節點

    那麼每個子樹可以看作是一組物品,對所有子樹做分組背包

    子樹v選擇保留k個點的話,那麼子樹i就要保留j-k個點.

    是以由狀态轉移:

    f(i, j) = max{ max{f(i,j-k) + f(v, k) - 1 | 1<=k<s} | v是i的兒子節點 }

    最終ans = min{ f(i, p)  |  1<=i<=n }

代碼

/**=====================================================
 *   This is a solution for ACM/ICPC problem
 *
 *   @source      : poj-1947 Rebuilding Roads
 *   @description : 樹形背包dp
 *   @author      : shuangde
 *   @blog        : blog.csdn.net/shuangde800
 *   @email       : [email protected]
 *   Copyright (C) 2013/08/19 14:30 All rights reserved. 
 *======================================================*/

#include 
   
    
#include 
    
     
#include 
     
      
#include 
      
       
#include 
       
         #include 
        
          #include 
         
           #define MP make_pair using namespace std; typedef pair
          
           PII; typedef long long int64; const int INF = 0x3f3f3f3f; const int MAXN = 160; vector
           
            adj[MAXN]; int n, p; int f[MAXN][MAXN], tot[MAXN]; int ans; int dp(int u) { // 計算子樹有幾個節點 tot[u] = 1; for (int i = 0; i < adj[u].size(); ++i) { int v = adj[u][i]; tot[u] += dp(v); } // init f[u][1] = adj[u].size(); // dp for (int i = 0; i < adj[u].size(); ++i) { int v = adj[u][i]; for (int s = tot[u]; s >= 1; --s) { for (int j = 1; j < s && j <= tot[v]; ++j) f[u][s] = min(f[u][s], f[u][s-j] + f[v][j] - 1); } } if (tot[u] >= p) ans = min(ans, f[u][p] + (u!=1)); return tot[u]; } int main(){ for (int i = 0; i <=n; ++i) adj[i].clear(); scanf("%d %d", &n, &p); for (int i = 0; i < n - 1; ++i) { int u, v; scanf("%d%d", &u, &v); adj[u].push_back(v); } memset(f, INF, sizeof(f)); ans = INF; dp(1); printf("%d\n", ans); return 0; }