May the force be with you!
posts - 52,  comments - 33,  trackbacks - 0
  我对树形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 *= 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 阅读(3454) 评论(1)  编辑 收藏 引用 所属分类: Problem Solving

FeedBack:
# re: 【树形DP】POJ1947 Rebuilding Roads 解题报告[未登录]
2009-09-24 21:37 | Simon
怎么WA了。。。。
无语。。。。
lz得程序貌似有点问题阿   回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


你是第 free hit counter 位访客




<2024年3月>
252627282912
3456789
10111213141516
17181920212223
24252627282930
31123456

常用链接

留言簿(4)

随笔分类(54)

随笔档案(52)

文章档案(1)

ACM/ICPC

技术综合

最新随笔

搜索

  •  

积分与排名

  • 积分 - 61525
  • 排名 - 357

最新评论

阅读排行榜

评论排行榜