Skip to content

「USACO 2010 March (Gold)」Great Cow Gathering

题解963 字
# 洛谷 # 动态规划 # USACO # 2010
检测到 KaTeX 加载失败，可能会导致文中的数学公式无法正常渲染。

#题面

#题目描述

Bessie 正在计划一年一度的奶牛大集会，来自全国各地的奶牛将来参加这一次集会。当然，她会选择最方便的地点来举办这次集会。

每个奶牛居住在 NN 个农场中的一个，这些农场由 N−1N - 1 条道路连接，并且从任意一个农场都能够到达另外一个农场。道路 ii 连接农场 AiA_i 和 BiB_i，长度为 LiL_i。集会可以在 NN 个农场中的任意一个举行。另外，每个牛棚中居住着 CiC_i 只奶牛。

在选择集会的地点的时候，Bessie 希望最大化方便的程度（也就是最小化不方便程度）。比如选择第 XX 个农场作为集会地点，它的不方便程度是其它牛棚中每只奶牛去参加集会所走的路程之和（比如，农场 ii 到达农场 XX 的距离是 2020，那么总路程就是 Ci×20C_i \times 20）。帮助 Bessie 找出最方便的地点来举行大集会。

#输入格式

第一行一个整数 NN。

第二到 N+1N + 1 行：第 i+1i + 1 行有一个整数 CiC_i。

第 N+2N+2 行到 2N2N 行：第 i+N+1i + N + 1 行为 33 个整数：Ai,BiA_i, B_i 和 LiL_i。

#输出格式

一行一个整数，表示最小的不方便值。

#输入输出样例

样例输入 #1

5
1
1
0
0
2
1 3 1
2 3 2
3 4 3
4 5 3

样例输出 #1

15

#提示

对于 100%100\% 的数据，1≤N≤1051 \leq N \leq 10^5，1≤Ai≤Bi≤N1 \leq A_i \leq B_i \leq N，0≤Ci,Li≤1030 \leq C_i, L_i \leq 10^3。

#思路

为一棵无根树指定根节点使得所有点的深度之和最小。

可以发现选定农场沿某条边 u→wvu \overset{w}{\to} v 移动时，uu 所在子树中的所有奶牛对答案的贡献都会增加 ww，vv 所在子树中的所有奶牛对答案的贡献都会减少 ww，答案的增加量为 w(size(u)−size(v))w (\mathrm{size}(u) - \mathrm{size}(v))。显然当选定农场位于树的重心时，答案为最小值（准确来说，应该将树的重心的定义中「最大子树的节点数最少」改为「最大的点权块最小」才成立）。

于是求树的重心的代码变成了这样（注意高亮行）：

C++
14
15
16
17
18
19
void dfs1(int u, int f) {
    siz[u] = c[u];

    for (auto e : g[u]) {
        int v = e.first,
            w = e.second;

最后求深度时不要忘了加上边权：

在 void dfs2(int, int) 中：C++
34
35
36
37
38
39
40
41
    int v = e.first,
        w = e.second;

    if (v == f) continue;

    dep[v] = dep[u] + w;
    dfs2(v, u);
}

#代码

C++
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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <iostream>
#include <vector>

using std::cin;
using std::cout;
const char endl = '\n';

const int N = 1e5 + 5;

int n, sum, root, c[N], siz[N], max_siz[N], dep[N];
long long ans;
std::vector<std::pair<int, int>> g[N];

void dfs1(int u, int f) {
    siz[u] = c[u];

    for (auto e : g[u]) {
        int v = e.first,
            w = e.second;

        if (v == f) continue;

        dfs1(v, u);

        siz[u] += siz[v];
        max_siz[u] = std::max(max_siz[u], siz[v]);
    }

    max_siz[u] = std::max(max_siz[u], sum - siz[u]);
}

void dfs2(int u, int f) {
    for (auto e : g[u]) {
        int v = e.first,
            w = e.second;

        if (v == f) continue;

        dep[v] = dep[u] + w;
        dfs2(v, u);
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;

    for (int i = 1; i <= n; i++) {
        cin >> c[i];

        sum += c[i];
    }

    for (int i = 1, u, v, w; i < n; i++) {
        cin >> u >> v >> w;

        g[u].emplace_back(v, w);
        g[v].emplace_back(u, w);
    }

    dfs1(1, 0);

    for (int i = 1; i <= n; i++) {
        if (!root || max_siz[i] < max_siz[root]) {
            root = i;
        }
    }

    dep[0] = -1;
    dfs2(root, 0);

    for (int i = 1; i <= n; i++) {
        ans += static_cast<long long>(c[i]) * dep[i];
    }

    cout << ans << endl;

    return 0;
}