Description D e s c r i p t i o n
传送门
有一棵点数为 N N 的树,树边有边权。给你一个在 ~ N N 之内的正整数 ,你要在这棵树中选择 K K 个点,将其染成黑色,并将其他的 个点染成白色。将所有点染色后,你会获得黑点两两之间的距离加上白点两两之间距离的和的收益。
问收益最大值是多少。
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 的左侧(很抽象的一个说法,就理解成把这条边摆中间,与 相连的那一部分都摆在左边,把与 v v 相连的都摆在右边,很明显,这两个部分是没有交集的)的黑点(白点同理)和 的右侧的黑点会产生两两配对(每个部分内部的匹配不属于这条边所产生的贡献),结果产生的收益就是 Blacku∗Blackv∗w B l a c k u ∗ B l a c k v ∗ w ,同理,我们就可以知道这条边能产生的收益可以表述为 (Blacku∗Blackv+Whiteu∗Whitev)∗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 为根的子树中有 个黑点能产生的最大贡献。
有了状态的定义,我们就额外要预处理出 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 是以 为根的子树的黑点数, q q 是以 为根的子树的黑点数。
- Blacku=k−q B l a c k u = k − q 容斥原理
- Blackv=q B l a c k v = q 已知条件
- Whiteu=n−size[v]−(k−q) W h i t e u = n − s i z e [ v ] − ( k − q ) 首先计算出除去以 v v 为根的子树中的结点之后全树还剩 个结点,再减去其中黑点的数目即 Blacku=k−q 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,p−q)+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,p−q) d ( u , p − q ) 的意义是 u u 的其他儿子及其子树的最大贡献。
最后,边界条件是 而其他都是 −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内容请搜索靠谱客的其他文章。
发表评论 取消回复