web analytics

poj1947-Rebuilding Roads[树形DP]

2017-02-18 09-44-27 的屏幕截图

poj 不能用bits也是很绝望啊。

Rebuilding Roads
Time Limit: 1000MS Memory Limit: 30000K
Total Submissions: 11612 Accepted: 5329
Description

The cows have reconstructed Farmer John's farm, with its N barns (1 <= N <= 150, number 1..N) after the terrible earthquake last May. The cows didn't have time to rebuild any extra roads, so now there is exactly one way to get from any given barn to any other barn. Thus, the farm transportation system can be represented as a tree.

Farmer John wants to know how much damage another earthquake could do. He wants to know the minimum number of roads whose destruction would isolate a subtree of exactly P (1 <= P <= N) barns from the rest of the barns.
Input

* Line 1: Two integers, N and P

* Lines 2..N: N-1 lines, each with two integers I and J. Node I is node J's parent in the tree of roads.
Output

A single line containing the integer that is the minimum number of roads that need to be destroyed for a subtree of P nodes to be isolated.
Sample Input

11 6
1 2
1 3
1 4
1 5
2 6
2 7
2 8
4 9
4 10
4 11
Sample Output

2
Hint

[A subtree with nodes (1, 2, 3, 6, 7, 8) will become isolated if roads 1-4 and 1-5 are destroyed.]
Source

USACO 2002 February

分析:

总觉得这道题要有什么状态,要有什么转移。不动态决策,当然会炸。
可以显然发现,这道题应该就是树形DP。

我们可以设 f[root][j]:表示,在第root节点,如果在此子树要有j个节点,最少要减去多少边。
设sum[i]以第i个节点为根,下面所有节点数。
然后我们思考边界情况,如果第root个节点是叶节点,所以这里我们f[root][1]=0。
然而其他节点f[root][1]=sum[i];

DFS时枚举
转移方程为 f[root][j]=min(f[root][j-k]+f[child][k]-1,f[root][j]);
PS:child 为root的一个子节点。
很像01背包的感觉。恩。就是这样。
注意:memset(f,0x3f3f3f,sizeof(f));

代码:这次写的时候尝试了一下namespace。很有趣///

Post a Comment

You must be logged in to post a comment.