2018 ICPC宁夏Factories 树形dp

传送门：https://nanti.jisuanke.com/t/A1767

题意

给一棵树，在树中选择k个节点，要求输出最小任意两点距离和。

思路

树、选择节点、统计距离-树形dp。 设f[u][i]为以u为根的字树中选择i个节点的贡献。 转移方程很容易看出：

$$f[u][i+j]=min(f[u][i+j],f[u][i]+f[v][j]+e[i].w*j*(k-j))$$

$e[i].w*j*(k-j)$是统计任意两点距离和的套路公式。

在方程中可以看出，f[u][i+j]是与f[u][i]有关的，所以不能正向转移，而要倒序转移。

但是倒序转移中会出现转移值出现被更改的问题。 所以需要一个辅助数组，这也是套路，但是不能memset，可以手写。

最后注意root不一定为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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
##include "bits/stdc++.h"

using namespace std;

typedef long long ll;

const int N = 2e5 + 10;
int n, k;

struct Edge {
    int v, next; ll w;
}e[N << 1];
int head[N << 1], cnt;

ll f[N][110]; // 以u为根的子树中选择k个叶子节点
ll temp[110];
int siz[N], d[N];

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

void dfs(int u, int fa) {
    if(d[u] == 1) {
        siz[u] = 1, f[u][0] = f[u][1] = 0;
        return ;
    }
    siz[u] = 0;
    for(int i = 1;i <= k; i++) f[u][i] = 2e18;
    for(int i = head[u]; i; i = e[i].next) {
        int v = e[i].v;
        if(v == fa) continue;
        dfs(v, u);
        siz[u] += siz[v];
        for(int p = 0;p <= min(siz[u], k); p++) temp[p] = 2e18;
        for(int p = 0;p <= min(siz[u], k); p++) {
            for(int q = 0;q <= siz[v] && p + q <= k; q++) {
                temp[p + q] = min(temp[p + q], f[u][p] + f[v][q] + e[i].w * q * (k - q));
            }
        }
        for(int p = 0;p <= min(siz[u], k); p++) f[u][p] = temp[p];
    }
}

void solve() {
    int _; scanf("%d",&_);
    int Case = 1;
    while(_--) {
        scanf("%d%d",&n,&k);
        cnt = 0;
        for(int i = 1;i <= n; i++) d[i] = 0, siz[i] = 0, head[i] = 0;
        for(int i = 1;i < n; i++) {
            int u, v; ll w; scanf("%d%d%lld",&u,&v,&w);
            add(u, v, w);
            add(v, u, w);
            d[u]++; d[v]++;
        }
        printf("Case ##%d: ",Case++);
        if(n == 2) {
            if(k == 2) printf("%lld\n",e[1].w);
            else printf("0\n");
            continue;
        }
        for(int i = 1;i <= n; i++) {
            if(d[i] > 1) {
                dfs(i, 0);
                printf("%lld\n",f[i][k]);
                break ;
            }
        }
    }
}

signed main() {
    solve();
}

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