BZOJ 1827 - [Usaco2010 Mar]gather 奶牛大集会

#动态规划 #树形动态规划

Published on 2016-04-10

描述

Bessie正在计划一年一度的奶牛大集会，来自全国各地的奶牛将来参加这一次集会。当然，她会选择最方便的地点来举办这次集会。每个奶牛居住在 $N(1\le N\le 100,000)$ 个农场中的一个，这些农场由 $N-1$ 条道路连接，并且从任意一个农场都能够到达另外一个农场。道路i连接农场 $A_i$ 和 $B_i(1 \le A_i \le N; 1 \le B_i \le N)$ ,长度为 $L_i(1 \le L_i \le 1,000)$ 。集会可以在 $N$ 个农场中的任意一个举行。另外，每个牛棚中居住者 $C_i(0 \le C_i \le 1,000)$ 只奶牛。在选择集会的地点的时候，Bessie希望最大化方便的程度(也就是最小化不方便程度)。比如选择第 $X$ 个农场作为集会地点，它的不方便程度是其它牛棚中每只奶牛去参加集会所走的路程之和，(比如，农场 $i$ 到达农场 $X$ 的距离是 20，那么总路程就是 $C_i*20$ 。帮助 Bessie找出最方便的地点来举行大集会。
考虑一个由五个农场组成的国家，分别由长度各异的道路连接起来。在所有农场中，3 号和 4 号没有奶牛居住。

样例输入

样例输出

分析

暴力的话 $O(n^2)$ 铁定爆炸，我们考虑已经求得一个点 $u$ 的答案，如何快速得到它的某个儿子 $v$ 的答案。
假设 $u$ 的答案是 $dis[u]$ ，那么集会点移到 $v$ ，对于所有的奶牛来说只有 2 种情况：

到集会点的距离变长
到集会点的距离变短

容易发现的是，无论变长还是变短，每个奶牛只会多／少走 $\text{cost}_{(u, v)}$ 。而且只有处于 $v$ 及其子树的牛会减，其余的都会加，所以很容易转移答案。
所以先求出根的答案，再次 dfs 即可。

代码

//  Created by Sengxian on 4/10/16.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  BZOJ 1827 树形DP
#include <algorithm>
#include <iostream>
#include <cctype>
#include <climits>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <vector>
#include <queue>
using namespace std;

inline int ReadInt() {
    static int n, ch;
    n = 0, ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) n = (n << 3) + (n << 1) + ch - '0', ch = getchar();
    return n;
}

typedef long long ll;
const int maxn = 100000 + 3;
struct edge {
    int to, cost;
    edge(int to, int cost): to(to), cost(cost) {}
};
vector<edge> G[maxn];
ll dis[maxn], ans = 1LL << 60;
int s[maxn], cnt[maxn], n;

int dfs(int u, int fa, int d) {
    s[u] = cnt[u], dis[0] += (ll)cnt[u] * d;
    for (int i = 0; i < G[u].size(); ++i) {
        edge &e = G[u][i];
        if (e.to != fa) s[u] += dfs(e.to, u, d + e.cost);
    }
    return s[u];
}

void dfs(int u, int fa) {
    ans = min(ans, dis[u]);
    for (int i = 0; i < G[u].size(); ++i) {
        edge &e = G[u][i];
        if (e.to != fa) {
            dis[e.to] = dis[u] + (ll)e.cost * (s[0] - s[e.to] * 2);
            dfs(e.to, u);
        }
    }
}

int main() {
    n = ReadInt();
    for (int i = 0; i < n; ++i) cnt[i] = ReadInt();
    for (int i = 0; i < n - 1; ++i) {
        int f = ReadInt() - 1, t = ReadInt() - 1, c = ReadInt();
        G[f].push_back(edge(t, c));
        G[t].push_back(edge(f, c));
    }
    dfs(0, -1, 0);
    dfs(0, -1);
    printf("%lld\n", ans);
    return 0;
}

BZOJ 1425 - SGU 421 k-th Product BZOJ 3696 - 化合物

Sengxian's Blog