我是靠谱客的博主 仁爱画板,这篇文章主要介绍【题解】BZOJ 4033 [HAOI2015]树上染色,现在分享给大家,希望可以做个参考。

Description D e s c r i p t i o n

传送门

有一棵点数为 N N 的树,树边有边权。给你一个在 0 ~ N N 之内的正整数 K ,你要在这棵树中选择 K K 个点,将其染成黑色,并将其他的 NK 个点染成白色。将所有点染色后,你会获得黑点两两之间的距离加上白点两两之间距离的和的收益。

问收益最大值是多少。

Solution S o l u t i o n

树形DP是很好看出来的。

但是确定状态并不是那么简单的事情了。

我们先考虑形如 <u,v,w> < u , v , w > <script type="math/tex" id="MathJax-Element-51"> </script> 的边能够产生什么贡献吧。

题目中描述,你会获得黑点两两之间的距离加上白点两两之间距离的和的收益。那么在 u u 的左侧(很抽象的一个说法,就理解成把这条边摆中间,与 u 相连的那一部分都摆在左边,把与 v v 相连的都摆在右边,很明显,这两个部分是没有交集的)的黑点(白点同理)和 v 的右侧的黑点会产生两两配对(每个部分内部的匹配不属于这条边所产生的贡献),结果产生的收益就是 BlackuBlackvw B l a c k u ∗ B l a c k v ∗ w ,同理,我们就可以知道这条边能产生的收益可以表述为 (BlackuBlackv+WhiteuWhitev)w ( B l a c k u ∗ B l a c k v + W h i t e u ∗ W h i t e v ) ∗ w

接下来就考虑状态,我们可以定义 d(i,j) d ( i , j ) 表示以 i i 为根的子树中有 j 个黑点能产生的最大贡献。

有了状态的定义,我们就额外要预处理出 size[] s i z e [ ] 数组来记录以某个结点为根时它的子树中的结点总和。

现在思路就清晰了。我们可以用 dfs() d f s ( ) 边预处理边跑DP。

dfs() d f s ( ) 中遍历一条边 <u,v> < u , v > <script type="math/tex" id="MathJax-Element-64"> </script> 结束时,枚举左右两边的黑点个数,计算出它所带来的贡献,将其并入答案。然而枚举也要讲求策略,我们令 p p 是以 u 为根的子树的黑点数, q q 是以 v 为根的子树的黑点数。

  • Blacku=kq B l a c k u = k − q 容斥原理
  • Blackv=q B l a c k v = q 已知条件
  • Whiteu=nsize[v](kq) W h i t e u = n − s i z e [ v ] − ( k − q ) 首先计算出除去以 v v 为根的子树中的结点之后全树还剩 nsize[v] 个结点,再减去其中黑点的数目即 Blacku=kq B l a c k u = k − q
  • Whitev=size[v]q W h i t e v = s i z e [ v ] − q 容斥原理

这样我们的得出来的值是 d(v,q) d ( v , q ) 而不是 d(u,p) d ( u , p ) 我们需要用 d(u,p)=max(d(u,p),d(u,pq)+d(v,q)+val) d ( u , p ) = m a x ( d ( u , p ) , d ( u , p − q ) + d ( v , q ) + v a l ) 来将其并入答案,其中 val v a l 就是这条边的贡献, d(u,pq) d ( u , p − q ) 的意义是 u u 的其他儿子及其子树的最大贡献。

最后,边界条件是 d(u,0)=d(u,1)=0 而其他都是 1 − 1 这应该很好理解。

Code C o d e

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define max(x, y) ((x) > (y) ? (x) : (y))
#define min(x, y) ((x) < (y) ? (x) : (y))
#define LL long long
#define MAXN 2010
struct edgetype {
int to, next, dist;
}edge[MAXN << 1];
int head[MAXN], cnt;
int n, k, size[MAXN];
LL d[MAXN][MAXN];
inline void AddEdge(int from, int to, int dist) {
edge[++cnt] = (edgetype){to, head[from], dist};
head[from] = cnt;
}
void dfs(int u, int p) {
size[u] = 1;
d[u][0] = d[u][1] = 0;
for (int i = head[u]; i; i = edge[i].next) {
int v = edge[i].to;
if (v == p) continue;
dfs(v, u);
size[u] += size[v];
}
for (int i = head[u]; i; i = edge[i].next) {
int v = edge[i].to, w = edge[i].dist;
if (v == p) continue;
for (int p = min(size[u], k); p >= 0; p--)
for (int q = 0; q <= min(p, size[v]); q++)
if (d[u][p - q] != -1) {
LL val = 1ll * (q * (k - q) + (size[v] - q) * (n - k + q - size[v])) * w;
d[u][p] = max(d[u][p], d[u][p - q] + d[v][q] + val);
}
}
}
int main() {
scanf("%d%d", &n, &k);
for (int i = 1; i < n; i++) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
AddEdge(u, v, w);
AddEdge(v, u, w);
}
memset(d, -1, sizeof d);
dfs(1, 0);
printf("%lldn", d[1][k]);
return 0;
}

最后

以上就是仁爱画板最近收集整理的关于【题解】BZOJ 4033 [HAOI2015]树上染色的全部内容,更多相关【题解】BZOJ内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(67)

评论列表共有 0 条评论

立即
投稿
返回
顶部