P1272 重建道路 树上背包

传送门：https://www.luogu.com.cn/problem/P1272

题意

$给一颗树，问最少删除几条边，可以使一颗子树含有p个节点？$

思路

树上问题，想必是树形dp。

设f[i][j]表示以i为根的子树，有j个节点最小删除边数。

状态转移： $$f[u][j] = min(f[u][j], f[u][j-k]+f[v][k]-1)$$

为什么要减1？ f[i][j]都是包含根节点，f[u][j-k]+f[v][k]中间会多出一条u和v相连的边。

最后答案是什么？

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

为什么除了根节点1，其他都要+1? 假设p=4的话，可以看见保留以2为根节点是明智的选择。

但是dp后f[2][4]=0，为什么呢？因为不需要删除任何边，但是1-2需要删除，所以+1。

总流程：

  1. 预处理f[i][1] = a[i]，a[i]为每个点的出度。
1
for(int i = 1;i <= n; i++) f[i][1] = a[i];
  1. dfs(1)，返回值为sum，表示以u为子树的节点个数，然后就可以转化成背包了。
1
2
3
4
5
6
7
8
9
int dfs(int u) {
    int sum = 1;
    for(auto v : g[u]) {
        int temp = dfs(v);
        sum += temp;
        // 背包。。。
    }
    return sum;
}
  1. 状态转移。
1
2
3
4
5
for(int j = sum;j >= 1; j--) {
    for(int k = 1;k < j; k++) {
        f[u][j] = min(f[u][j], f[u][i - k] + f[v][k] - 1);
    }
}

Code

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
##include "bits/stdc++.h"
using namespace std;

const ll INF = 0x3f3f3f3f;
const int N = 1e3 + 10;

vector<vector<int>> f(N, vector<int>(N, INF));
vector<int> g[N];

int dfs(int u) {
    int sum = 1;
    for(auto v : g[u]) {
        int temp = dfs(v);
        sum += temp;
        for(int j = sum;j >= 1; j--) {
            for(int k = 1;k < j; k++) {
                f[u][j] = min(f[u][j], f[u][j - k] + f[v][k] - 1);
            }
        }
    }
    return sum;
}

void solve() {
    int n, p; cin >> n >> p;
    vector<int> a(n + 1);
    for(int i = 1;i <= n - 1; i++) {
        int u, v; cin >> u >> v;
        a[u]++;
        g[u].eb(v);
    }
    for(int i = 1;i <= n; i++) f[i][1] = a[i];
    dfs(1);
    int ans = f[1][p];
    for(int i = 2;i <= n; i++) {
        if(f[i][p] < ans) ans = f[i][p] + 1;
    }
    cout << ans << endl;
}

signed main() {
    solve();
}

本文作者：jujimeizuo
本文地址： https://blog.jujimeizuo.cn/2021/03/21/luogu-p1272/
本博客所有文章除特别声明外，均采用 CC BY-SA 3.0 协议。转载请注明出处！