P3177-[HAOI2015]树上染色
题目:
题目描述:
有一棵点数为 $n$ 的树，树边有边权。给你一个在 $0 \sim n$ 之内的正整数 $k$ ，你要在这棵树中选择 $k$ 个点，将其染成黑色，并将其他 的 $n-k$ 个点染成白色。将所有点染色后，你会获得黑点两两之间的距离加上白点两两之间的距离的和的受益。问受益最大值是多少。
输入格式:
第一行包含两个整数 $n, k$。
第二到 $n$ 行每行三个正整数 $fr, to, dis$，表示该树中存在一条长度为 $dis$ 的边 $(fr, to)$。输入保证所有点之间是联通的。
输出格式:
输出一个正整数，表示收益的最大值。
样例:
样例输入 1:
样例输出 1:
思路:
实现:
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
| #include "ybwhead/ios.h"
int n, k;
const int maxn = 2e3 + 10;
struct edge
{
int v, w, nxt;
} e[maxn << 1];
long long f[maxn][maxn];
int head[maxn], tot;
void __ADD(int u, int v, int w)
{
e[++tot] = (edge){v, w, head[u]};
head[u] = tot;
}
void add(int u, int v, int w)
{
__ADD(u, v, w);
__ADD(v, u, w);
}
int sz[maxn];
void dfs(int u, int fa)
{
sz[u] = 1;
f[u][0] = f[u][1] = 0;
for (int i = head[u]; i; i = e[i].nxt)
{
int v = e[i].v;
if (v == fa)
continue;
dfs(v, u);
sz[u] += sz[v];
long long w = e[i].w;
for (int i = min(k, sz[u]); i >= 0; i--)
{
for (int j = 0; j <= min(i, sz[v]); j++)
{
if (f[u][i - j] != -1)
{
long long val = w * (long long)j * (k - j) + w * (long long)(sz[v] - j) * (n - k + j - sz[v]);
f[u][i] = max(f[u][i], f[u][i - j] + f[v][j] + val);
}
}
}
}
return;
}
int main()
{
yin >> n >> k;
for (int i = 1; i < n; i++)
{
int a, b, c;
yin >> a >> b >> c;
add(a, b, c);
}
memset(f, -1, sizeof(f));
dfs(1, 0);
yout << f[1][k] << endl;
return 0;
}
|