「HAOI 2015」树上染色

发表于 | | 阅读次数:
字数统计: 637 字

Description

题目链接：BZOJ 4033

有一棵 $N$ 个节点的树（有边权），选择 $K$ 个点染成黑色，其他点染成白色。最后得到的收益为“黑点两两之间的距离和，白点两两之间的距离和”之和，要求最大化收益。

数据范围：$0\le K\le N\le 2000$

Solution

显然这是一道树形 $\text{DP}$ 题目，我们设 $f[i][j]$ 表示以 $i$ 为根节点的树中染了 $j$ 个黑点获得的最大收益。

在处理完子树 $v$ 中，我们加入边 $E(u,v)$（$u$ 是 $v$ 的父亲），则 $E(u,v)$ 的贡献为

每次树形 $\text{DP}$ 时，先把子树 $v$ 和以 $u$ 为根的树中已经计算完的部分进行 $01$ 背包合并，最后计算 $u$ 对其父亲的贡献即可（以便接下来的递归计算）。

时间复杂度：$O(N^2)$

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
 
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N=2005;
int n,m,tot,hd[N],sz[N];
long long f[N][N],val[N];
struct Edge{
    int to,nxt,w;
}e[N<<1];

void add(int u,int v,int w) {
    e[++tot].to=v;
    e[tot].w=w;
    e[tot].nxt=hd[u];
    hd[u]=tot;
}
void dfs(int u,int fa) {
    f[u][0]=f[u][1]=0; sz[u]=1;
    for(int i=hd[u];i;i=e[i].nxt) {
        int v=e[i].to;
        if(v==fa) continue;
        val[v]=e[i].w;
        dfs(v,u);
        for(int k=min(sz[u],m);k>=0;--k)
            for(int j=min(sz[v],m-k);j>=0;--j)
                f[u][k+j]=max(f[u][k+j],f[u][k]+f[v][j]);
        sz[u]+=sz[v];
    }
    for(int i=0;i<=min(sz[u],m);++i)
        f[u][i]+=val[u]*(i*(m-i)+(sz[u]-i)*(n-m-(sz[u]-i)));
}
int main() {
    scanf("%d%d",&n,&m);
    for(int u,v,w,i=1;i<n;++i) {
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w); add(v,u,w);
    }
    for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) f[i][j]=-(1LL<<60);
    dfs(1,0);
    printf("%lld\n",f[1][m]);
    return 0;
}

Complexity

看起来树形 $\text{DP}$ + 背包的复杂度为 $O(N^3)$，但是实际上我们发现枚举的范围是 $0\le k\le sz[v]$，$0\le j-k\le sz[u]-sz[v]$，那么总的枚举次数为 $\sum(sz[u]-sz[v])\times sz[v]$。

而 $\sum sz[v]=sz[u]$，那么复杂度为 $sz[u]^2-\sum sz[v]^2$。以此向上推，则到根节点时复杂度为 $O(N^2)$。

0%