[HDOJ1055] Color a Tree (贪心)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1055

题意:一棵n个点的树,每个点有权重$w_i$,现在要求给树上的点从1~n打标记$id_i$, 使得$\sum_{i=1}^nw_i\times id_i$最小。

http://acm.hdu.edu.cn/showproblem.php?pid=1055

贪心,从树根开始,每次合并当前权重最大的点和它的父亲,合并之后的节点权重为总权重/子节点数。

由于每次合并都会导致当前父亲节点的子孙们权重+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
#include <bits/stdc++.h>
using namespace std;

const int maxn = 10100;
bool vis[maxn];
int n, rt;
struct {
int tot, pre;
double val, contain;
} f[maxn];

signed main() {
// freopen("in", "r", stdin);
int u, v;
while (~scanf("%d%d", &n, &rt) && n + rt) {
memset(vis, 0, sizeof vis);
int ret = 0;
for (int i = 1; i <= n; i++) {
scanf("%d", &f[i].tot);
ret += f[i].tot;
f[i].val = f[i].tot;
f[i].contain = 1;
}
for (int i = 1; i < n; i++) {
scanf("%d%d", &u, &v);
f[v].pre = u;
}
for (int i = 1; i < n; i++) {
int id = -1;
double hi = -1e9;
for (int j = 1; j <= n; j++) {
if (hi < f[j].val && j != rt) {
id = j;
hi = f[j].val;
}
}
int pre = f[id].pre;
f[id].val = -1E9;
for (int j = 1; j <= n; j++) {
if(f[j].pre == id) {
f[j].pre = pre;
}
}
ret += f[id].tot * f[pre].contain;
f[pre].contain += f[id].contain;
f[pre].tot += f[id].tot;
f[pre].val = f[pre].tot / f[pre].contain;
}
printf("%d\n", ret);
}
return 0;
}