「IOI 2005」Riv

题目大意：给定一棵 $n$ 个节点的树，每条边的长度为 $d_i$，每个节点会产 $w_i$ 棵木头，并向上运输到第一个遇到的伐木场，总费用为所有木头的路程总和，根节点初始时为伐木场，请你再选 $k$ 个节点建立伐木场，使得运输木料的总花费最小。$n \leq 100, k \leq 50$

设 $f[i][j][k]$ 表示在 $i$ 的子树中（不包括 $i$）建 $k$ 个伐木场，$i$ 的祖先中最近的一个建有伐木场的节点为 $j$ 且 $i$ 处不建场的最小花费，$g[i][j][k]$ 表示 $i$ 处建场的最小花费。

#include <cstdio>
#include <algorithm>

using std::min;

const int N = 105, M = 55;
int f[N][N][M], g[N][N][M], head[N], nxt[N], dis[N], d[N], w[N], sta[N], top, tot, n, m;

int read() {
    int x = 0; char c = getchar();
    while (c < '0' || c > '9') c = getchar();
    while (c >= '0' && c <= '9') {
        x = (x << 3) + (x << 1) + (c ^ 48);
        c = getchar();
    }
    return x;
}
void dfs(int u) {
    sta[++top] = u;
    for (int v = head[u]; v; v = nxt[v]) {
        dis[v] = dis[u] + d[v];
        dfs(v);
        for (int i = 1; i <= top; ++i)
            for (int j = m; j >= 0; --j) {
                f[u][sta[i]][j] += f[v][sta[i]][0];
                g[u][sta[i]][j] += f[v][u][0];
                for (int k = 0; k <= j; ++k) {
                    f[u][sta[i]][j] = min(f[u][sta[i]][j], f[u][sta[i]][j-k] + f[v][sta[i]][k]);
                    g[u][sta[i]][j] = min(g[u][sta[i]][j], g[u][sta[i]][j-k] + f[v][u][k]);
                }
            }
    }
    for (int i = 1; i <= top; ++i) //合并f与g, 因为之后就不在乎u有没有建伐木场, 只关心u和u的子树建了多少
        for (int j = 0; j <= m; ++j) {
            if (j == 0) f[u][sta[i]][j] += w[u] * (dis[u] - dis[sta[i]]);
            else f[u][sta[i]][j] = min(f[u][sta[i]][j] + w[u] * (dis[u] - dis[sta[i]]), g[u][sta[i]][j-1]);
        }
    --top;
}

int main() {
    n = read(), m = read();
    for (int i = 1, j; i <= n; ++i) {
        w[i] = read(), j = read(), d[i] = read();
        nxt[i] = head[j], head[j] = i;
    }
    dfs(0);
    printf("%d\n", f[0][0][m]);
    return 0;
}

时间复杂度 $O(n^2k^2)$