题解 P1272 【重建道路】

· · 题解

1.对题目的理解

通过读题，很明显此题是一道树形DP，而且是比较经典的树形背包问题，本质上是分组背包，所谓分组背包，即在选择物品的时候，一开始将物品分为好几组，在选择时，可以从每一组中至多选择一件物品，问如何获得最大的价值，所以我们每次可以枚举这个组数，用i表示第几组，用j表示体积，用k来表示选择的物品，伪代码如下

for (int i = 0到组数)
    for (int j = max_v到0)
        for (int k = 此组所有物品)
            f[j] = max (f[j], f[j - v[k]] + w[k])

在树也是同样的道理，每个子树其实就是每一个组，在里面选择，但不同的是，在这里我们用dfs来实现

2.大体思路

1.对于状态转移方程和初始化我也不想多说，因为别人的题解都有，这里我们用f\left ( i,j \right )来表示第i个点为跟的子树，保留j个点（包括自己）删去边的最小值，我们用a[i]l来记录出度， 也就是几个儿子，因此：

初始化：

f\left ( i,1 \right ) = a[i]

方程：

f\left ( now,j \right ) = max\left ( f\left ( now,j \right ),f\left ( now,j - k \right ) + f\left ( v,k \right )-1 \right )

其实这个转移方程没什么特殊的，其实就是一个树上背包的板子，你肯定会问：板子题为什么还这么难做，因为这个题的坑点稍微有一点多，思维难度稍微有一点大，比如说状态转移方程中的-1，还有其他的一些东西在接下来的讲解中就会更加深入

2.我跟别人的题解其实不太一样，我不知道是我跟大家不一样还是大家都没有读题，其实题目有说：每行2个整数I和J，表示节点I是节点J的父节点，也就是说这是一棵树，而且是有根的，所以我们并不用像其他题解那样人云亦云，全都去建双向边，既然有根，那么我们直接可以建单向边解决，而且更加轻松，很显然，跟没有入度，所以我们可以记录一下每一个点的入度b[i]，所以我们找根可以这样找，顺便初始化：

for (int i = 1; i <= n; i ++)
{
    if (!b[i]) root = i;
    f[i][1] = a[i];
}

3.现在我们可以开始DP了，找出根以后直接从根开始DP，一路往下，这里我们可以开两次变量，一个是temp，一个是sum，temp表示的当前的v的子树中的节点个数，sum表示当前的now节点下所有的子树的节点个数，每次遍历完一个v就累加，其实也就是背包的一个容量罢了，每次return一下sum，由于这个节点个数要包括自己，所以初始值我们必须设置为1

4.重头戏来了，一个最大的问题，为什么我们的状态转移方程中最后要减去1呢？我先在这里放一张图，有助于理解

这张图很显然就是我们的样例而已，他可以很好的说明问题，举个例子，比如说我们的v是5这个节点的时候，我们在更新f\left ( 1,2 \right )时，可以分给他保存一个，1节点保存一个那么就是f\left ( 1,1 \right ) + f\left ( 5,1 \right ) = 4 + 0 = 5了，而很显然答案是3，这是为什么呢，这是因为没有考虑v和now节点之间相连的那一条边，很显然是不可以拆掉的，所以拆掉的边数必须要减去1，代码如下：

inline int dfs (int now)
{
    int temp; int sum = 1;
    for (int i = head[now]; i; i = edge[i].next)
    {
        int v = edge[i].v;
        temp = dfs (v); sum += temp;
        for (int j = sum; j >= 1; j --)
            for (int k = 1; k < j; k ++)
                    f[now][j] = min (f[now][j], f[now][j - k] + f[v][k] - 1);
    }
    return sum;
}

5.那么大部分的任务我们都完成了，剩下的就是处理答案，我一开始也犯了一个小错误，直接输出了f\left ( root,p \right )，拿了72分，但这个显然是不对的，因为我们要获得一颗子树，并不是非得从根节点，因此我们需要枚举每一个节点为根的小子树，看看哪一个是最小的

for (int i = 1; i <= n ; i ++)
{
    if (f[i][p] < ans) ans = f[i][p] + 1;
}

6.你会有疑问了，为什么是 + 1呢，这就是本题的另外一个坑点，你可以拉上去看上面那一张图片，我们再举个例子，样例别的不变，如果p变成了4怎么办，我们用眼睛看可以很清楚的看到，保留整颗以2为根的子树是最明智的，只需要砍去一条边，然而我们DP完之后f\left ( 2,4 \right )的值却为0，因为不需要砍掉任何边，而需要砍掉上面的那一条边，这里我们就忽略掉了，所以需要+1来解决问题

3.完整代码

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>

#define N 310

using namespace std;

inline int read ()
{
    int f = 1, x = 0;
    char ch;
    do {ch = getchar (); if (ch== '-') f = -1;} while (ch < '0' || ch > '9');
    do {x = x * 10 + ch - '0'; ch = getchar ();} while (ch >= '0' && ch <= '9');
    return f * x;
}

struct node
{
    int u, v, next;
} edge[N];
int n, p;
int cnt, head[N];
int f[N][N];
int a[N];
bool b[N];
int root;
int ans = 0x3f3f3f3f;

inline void add (int u, int v)
{
    edge[++cnt].v = v;
    edge[cnt].next = head[u];
    head[u] = cnt;
}

inline int dfs (int now)
{
    int temp; int sum = 1;
    for (int i = head[now]; i; i = edge[i].next)
    {
        int v = edge[i].v;
        temp = dfs (v); sum += temp;
        for (int j = sum; j >= 1; j --)
            for (int k = 1; k < j; k ++)
                    f[now][j] = min (f[now][j], f[now][j - k] + f[v][k] - 1);
    }
    return sum;
}

int main ()
{
    n = read (); p = read ();
    int x, y;
    for (int i = 1; i <= n - 1; i ++)
    {
        x = read (); y = read ();
        a[x] ++; b[y] = 1;
        add (x, y);
    }
    memset (f, 0x3f3f3f3f, sizeof (f));
    for (int i = 1; i <= n; i ++)
    {
        if (!b[i]) root = i;
        f[i][1] = a[i];
    }
    dfs (root);
    ans = f[root][p];
    for (int i = 1; i <= n ; i ++)
    {
        if (f[i][p] < ans) ans = f[i][p] + 1;
    }
    printf ("%d", ans);
    return 0;
}

我喜欢我的码风

可以抄题解，但是你要学会哦

4.推几道类似的树上背包P1273，P2014，P2015