P1272 重建道路

题意

给出一颗有 n 个节点的树，求问分解出一个含有 p 个节点的子树最少需要删去多少条边。

思路

假设我们要以一个节点为根，那么我们不妨定义 f[i , j] 用以表示节点 i 包括其根形成了具有 j 个结点的子树。

那么对于一个节点 u，我们可以直接得到f[u ,1] 的值为节点 u 所连接子树的 个数，也就是说，我们将这个节点所连接所有的子树都给删去所得到的最小边。

在已经加入一定的节点的情况下。我们加入u 的一个子树 x 我们就可以得到一个转移方程 f[u ,i + j] = min(f[u ,i] + f[x ,j] - 1)。

那么我们只需要遍历一遍即可得出答案。

Code

#include <cstring>
#include <iostream>
#include <vector>
using namespace std;

vector<int> E[160];
int f[160][160];
int sz[160];

void dfs(int u) {
    sz[u] = 1;
    f[u][1] = E[u].size();
    for (auto x : E[u]) {
        dfs(x);
        for (int i = sz[u]; i > 0; i--)
            for (int j = 1; j <= sz[x]; j++)
                f[u][i + j] = min(f[u][i + j], f[u][i] + f[x][j] - 1);

        sz[u] += sz[x];
    }
}

int main() {
    int n, p;
    cin >> n >> p;

    for (int i = 1; i < n; i++) {
        int x, y;
        cin >> x >> y;
        E[x].push_back(y);
    }

    memset(f, 0x3f, sizeof(f));
    dfs(1);
    int minn = 1e9;

    for (int i = 1; i <= n; i++) {
        if (i == 1) minn = min(minn, f[i][p]);
        if (i != 1) minn = min(minn, f[i][p] + 1);
    }

    cout << minn << '\n';

    return 0;
}