我對樹形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 閱讀(3537)
評論(1) 編輯 收藏 引用 所屬分類:
Problem Solving