[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;
}