pku1947 Rebuilding Roads

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

DP，树状DP

一棵节点为N的树，去掉最少的边，满足剩下树中，有一棵树的节点数为P

还要用分组背包优化，分组背包自己想的思路，写的比较难看。。。

dp[i][j]：表示以节点i为根的树，如果想要保证有j个节点，至少要去掉的边数

对于每组dp[i]，只能选一种j，如果不选这一组，也要多消耗1的费用

叶子节点初始化：dp[i] = {0, 1, 正无穷, 正无穷.......}；

之后看了一下背包九讲：

还可以把每个节点看成一个物品，那就成了背包九讲中的“泛化物品”背包，之前没理解泛化的意思，现在有了一个大概的理解了

安背包九讲的定义，这题可以简述成：有依赖的泛化物品背包问题吧。。。

  1 #include <stdio.h>
  2 #include <vector>
  3 #define N 156
  4 
  5 using namespace std;
  6 
  7 int n, p, mark[N];
  8 vector<int> a[N], dp[N];
  9 const int inf = 1234;
 10 
 11 int min(int x, int y)
 12 {
 13     return x<y? x: y;
 14 }
 15 
 16 int inf_limit(int x)
 17 {
 18     return x>inf? inf: x;
 19 }
 20 
 21 vector<int> pack(vector<int> b, vector<int> c)
 22 {
 23     int i, j;
 24     vector<int> r;
 25     for(i=0; i<=p; i++) 
 26     {
 27         r.push_back(inf);
 28     }
 29 
 30     for(i=0; i<=p; i++)
 31     {
 32         for(j=0; j<=p && i+j<=p; j++)
 33         {
 34             r[i+j] = min(r[i+j], inf_limit(c[i]+b[j]));
 35         }
 36     }
 37     return r;
 38 }
 39 
 40 void f(int x, vector<int> b)
 41 {
 42     int i, j;
 43     vector<int> c;
 44     for(i=0; i<=p; i++)
 45     {
 46         c.push_back(inf);
 47         dp[x].push_back(inf);
 48     } 
 49     if(b.size() == 0)
 50     {
 51         dp[x][0] = 1;
 52         dp[x][1] = 0;
 53         return;
 54     }
 55     c = dp[b[0]];
 56     for(i=1; i<b.size(); i++)
 57     {
 58         j = b[i];
 59         c = pack(c, dp[j]);
 60     }
 61     dp[x][0] = 1;
 62     for(i=1; i<=p; i++)
 63     {
 64         dp[x][i] = c[i-1];
 65     }
 66 }
 67 
 68 void dfs(int x)
 69 {
 70     int i, j;
 71     vector<int> b;
 72     for(i=0; i<a[x].size(); i++)
 73     {
 74         j = a[x][i];
 75         if(mark[j] == 0)
 76         {
 77             b.push_back(j);
 78             mark[j] = 1;
 79             dfs(j);
 80         }
 81     }
 82     f(x, b);
 83     return;
 84 }
 85 
 86 int main()
 87 {
 88     int i, j, x, y, root;
 89     int result;
 90     scanf("%d%d", &n, &p);
 91     for(i=1; i<=n; i++)
 92     {
 93         mark[i] = 1;
 94         a[i].clear();
 95         dp[i].clear();
 96     }
 97     for(i=1; i<=n-1; i++)
 98     {
 99         scanf("%d%d", &x, &y);
100         a[x].push_back(y);
101         mark[y] = 0;
102     }
103     for(i=1; i<=n; i++)
104     {
105         if(mark[i] == 1)
106         {
107             root = i;
108         }
109     }
110     dfs(root);
111     result = dp[root][p];
112     for(i=1; i<=n; i++)
113     {
114         result = min(result, dp[i][p]+1);
115     }
116     printf("%d\n", result);
117     return 0;
118 }