我对树形DP早有耳闻，不过没有做过相应的题目。最近看集合DP不怎么懂，所以换看树形DP，昨天看到一个题目AC了结果发现跟树形DP的思想不太像，这道题目就完全是基础的树形DP题了，纪念一下，呵呵。
题目来源：USACO 2002 February
题目提交方式：POJ1947
http://acm.pku.edu.cn/JudgeOnline/problem?id=1947
题目描述：
对于一棵树，问删除一些边使得它的一棵子树正好有p个节点，问最少要删除多少边？
输入：
N（1<=N<=150)，P(1<=P<=N),接下来是N－1条边的描述（父亲节点在前）。
输出：
ANS(要删除的最小边数）
解题思路：
建树比较简单，然后就是设计状态转移方程：
对于一个节点i：用函数f[i][j]表示以它为根节点能得到j个节点的子树需要删除的最小边数。
状态转移方程：f[i][j+k] = min(f[i][k]+f[c][j]), c为i的儿子节点。
最后结果为根f[root][p]和f[i][p]+1(1<=i<=n)中的最小值。
我的代码：
1 /*********************************************************************
2 Author: littlekid
3 Created Time: 2008-3-1 11:38:58
4 Problem Source: POJ1947
5 Description:
6 ********************************************************************/
7 # include <iostream>
8 using namespace std;
9
10 # define N 155
11
12 # define TEST
13
14 const int LARGE_NUMBER = 11111;
15
16 typedef struct _node {
17 _node *next;
18 int id;
19 };
20
21 _node vect[ N ];
22 int n, p, root, ans, f[ N ][ N ];
23
24 void initialize(int n)
25 {
26 for (int i = 1; i <= n; i ++)
27 {
28 vect[i].id = 0;
29 vect[i].next = NULL;
30 }
31 }
32
33 void insert(int v, int u)
34 {
35 _node *p;
36 p = new _node;
37 p->id = u;
38 p->next = vect[v].next;
39 vect[v].next = p;
40 vect[v].id ++;
41 }
42
43 void del(_node *p)
44 {
45 if (p == NULL) return ;
46 del(p->next);
47 delete p;
48 }
49
50 void clear(int n)
51 {
52 for (int i = 1; i <= n; i ++)
53 {
54 del(vect[i].next);
55 vect[i].next = NULL;
56 }
57 }
58
59
60 void init()
61 {
62 int s, t;
63 int flag[n+1];
64 memset(flag, false, sizeof(flag));
65 for (int i = 1; i < n; i ++)
66 {
67 scanf("%d %d", &s, &t);
68 insert(s, t);
69 flag[t] = true;
70 }
71 t = 1;
72 while (flag[t]) t ++;
73 root = t;
74 }
75
76 void output()
77 {
78 printf("%d\n", ans);
79 }
80
81 void DFS(int now)
82 {
83 _node *q = vect[now].next;
84 int tmp;
85 for (int i = 0; i <= p; i ++) f[now][i] = LARGE_NUMBER;
86 f[now][1] = vect[now].id;
87 q = vect[now].next;
88 while (q != NULL)
89 {
90 DFS(q->id);
91 for (int j = p-1; j >= 0; j --)
92 {
93 if (f[now][j] < LARGE_NUMBER)
94 {
95 for (int k = 1; k < p; k ++)
96 {
97 if (f[q->id][k] < LARGE_NUMBER)
98 {
99 tmp = f[now][j] + f[q->id][k] -1;
100 if (tmp < f[now][j+k])
101 {
102 f[now][j+k] = tmp;
103 }
104 }
105 }
106 }
107 }
108 q = q->next;;
109 }
110 }
111
112 void dp()
113 {
114 DFS(root);
115
116 #ifdef TEST
117 for (int i = 1; i <= n; i ++)
118 {
119 for (int j = 1; j <= p; j ++)
120 {
121 cout << f[i][j] << " ";
122 }
123 cout << endl;
124 }
125 #endif
126
127 ans = f[root][p];
128 for (int i = 1; i <= n; i++)
129 {
130 if (f[i][p] < ans) ans = f[i][p]+1;
131 }
132 }
133
134 int main()
135 {
136 while (scanf("%d %d", &n, &p) != EOF)
137 {
138 initialize(n);
139 init();
140 dp();
141 output();
142 clear(n);
143 }
144 return 0;
145 }
146
147
posted on 2008-03-01 14:16
R2 阅读(3500)
评论(1) 编辑 收藏 引用 所属分类:
Problem Solving