[PKU1947]Rebuilding Roads

这题也是USACO 2002 February 的题目。

这题显然是树形动规，状态表示也十分容易想到，用f[i, j]表示以i为根的子树，删除j个节点的最小代价。问题的关键就是如何求解。

由于是多叉树，所以不能够直接枚举每一个孩子节点分配多少删除目标（直接枚举的话莫非是要写一个全排列？？），考虑将多叉树转成二叉树，左孩子右兄弟，那么只要考虑孩子和兄弟之间的关系。

如果i这个节点和i的父节点的联系被切断，那么显然不用考虑孩子节点了（左孩子），直接考虑把j-son[i]-1删除任务交给兄弟（右孩子）。

否则如果给孩子（左孩子）分配了k个删除任务，那么兄弟（右孩子）就得完成j-k个任务。

另外，这题可以是从大树中剪除一棵子树或者分离出一棵子树，所以答案还得枚举以谁为根最优。

注意边界情况的处理。

PS.这题也可以在树形DP里面套一个背包。 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

#include <cstdio>
#include <cstring>
#include <algorithm>

const int INF(0x3FFFFFFF);
struct tree_node
{
  int left, right;
} tree[150];
int root, n, p, last[150], f[150][150], son[150];
bool notroot[150];
int dp(const int i, const int j)
{
  if (i == -1) return j == 0 ? 0 : INF;
  if (j == 0) return 0;
  if (j < 0) return INF;
  if (f[i][j] != -1) return f[i][j];
  int res = 1+dp(tree[i].right, j-son[i]-1);
  for (int k = 0; k <= j; ++k)
    res = std::min(res,
        dp(tree[i].left, k)+dp(tree[i].right, j-k)
        );
  return f[i][j] = res;
}
int getson(const int root)
{
  int node = tree[root].left;
  while (node != -1)
  {
    son[root] += 1+getson(node);
    node = tree[node].right;
  }
  return son[root];
}
int main()
{
  memset(f, 255, sizeof(f));
  memset(tree, 255, sizeof(tree));
  scanf("%d%d", &n, &p);
  for (int i = 0, x, y; i < n-1; ++i)
  {
    scanf("%d%d", &x, &y);
    --x, --y;
    (last[x] ? tree[last[x]].right : tree[x].left) = y;
    last[x] = y;
    notroot[y] = true;
  }
  for (; root < n && notroot[root]; ++root);
  getson(root);

  int ans = dp(tree[root].left, n-p);
  for (int i = 0; i < n; ++i)
    if (i != root)
      ans = std::min(ans, dp(tree[i].left, son[i]+1-p)+1);
  printf("%d", ans);
}

Comments