POJ 1947 - Rebuilding Roads 樹型DP(泛化背包轉移)..

dp[x][y]表示以x為根的子樹要變成有y個點..最少需要減去的邊樹... 最終ans=max(dp[i][P]+t)  < i=(1,n) , t = i是否為整棵樹的根 >

     更新的時候分為兩種情況..一種是要從其這個孩子轉移過來...枚舉做01背包..更新出每個狀態的最小值..或者說直接砍掉這個孩子..那麼只需將所有的狀態多加個砍邊...     

     這裡的枚舉做01背包..意思是由於葉子節點要放多少進去不確定..葉子節點要放的大小以及本節點的空間都在枚舉更新...這種概念就是泛化背包..本質上是01背包.做多次01背包

     注意到枚舉空間的順序.這樣能保證更新的時候不出現混亂....

Program:

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<set>
#include<ctime>
#include<algorithm>
#include<queue>
#include<cmath>
#include<map>
#define oo 100000007
#define ll long long
#define pi acos(-1.0)
#define MAXN 155
using namespace std;
vector<int> Tree[MAXN];
int dp[MAXN][MAXN],N,P,ans;
bool root[MAXN];
int dfs(int x)
{
      int i,j,y,m=Tree[x].size(),num=1,t,update;  
      for (i=0;i<=P;i++) dp[x][i]=oo;
      dp[x][1]=0;
      for (i=0;i<m;i++)
      {
             y=Tree[x][i];
             num+=dfs(y); 
             for (t=P;t>=1;t--)
             {
                    update=dp[x][t]+1;
                    for (j=1;j<=t;j++)
                       update=min(update,dp[x][t-j]+dp[y][j]);
                    dp[x][t]=update;
             }  //泛化背包轉移 
      }
      t=0;
      if (!root[x]) t++;
      if (dp[x][P]!=-1) ans=min(dp[x][P]+t,ans);
      return num;
}
int main()
{
      int i; 
      while (~scanf("%d%d",&N,&P))
      {
            for (i=1;i<=N;i++) Tree[i].clear();
            memset(root,true,sizeof(root));
            for (i=1;i<N;i++)
            {
                   int x,y;
                   scanf("%d%d",&x,&y);
                   Tree[x].push_back(y);
                   root[y]=false;
            }
            for (i=1;i<=N;i++)
               if (root[i]) break;
            ans=oo;
            dfs(i);
            printf("%d\n",ans);
      }
      return 0;
}