题面

Bzoj

洛谷

题解

这种求比值最大就是$0/1$分数规划的一般模型。

这里用二分法来求解最大比值，接着考虑如何$check$，这里很明显可以想到用树形背包$check$，但是时间复杂度要优化成$O(n^2)$的，可以参考之前写的这篇博客

#include <cstdio>

#include <algorithm>

using std::min;

using std::max;

const int N = 3e3 + 10, inf = 1e9 + 7;

const double eps = 1e-5;

int n, K, s[N], p[N], son[N][N], dfn[N], time, nx[N];

int from[N], to[N], nxt[N], cnt;//Edges

double f[N][N], d[N];

inline void addEdge (int u, int v) {

    to[++cnt] = v, nxt[cnt] = from[u], from[u] = cnt;

}

inline void upt(double &a, double b) {

    if (a < b) a = b;

}

void dfs (int u) {

    dfn[u] = time++;

    for (int i = from[u]; i; i = nxt[i]) dfs(to[i]);

    nx[dfn[u]] = time;

}

inline bool check (double k) {

    for (int i = 1; i <= n; ++i)

        d[dfn[i]] = p[i] - k * s[i];

    for (int i = 1; i <= n + 1; ++i)

        for (int j = 0; j <= K; ++j)

            f[i][j] = -inf;

    for (int i = 0; i <= n; ++i)

        for (int j = 0; j <= min(i, K); ++j) {

            upt(f[i + 1][j + 1], f[i][j] + d[i]);

            upt(f[nx[i]][j], f[i][j]);

        }

    return f[n + 1][K] >= eps;

}

int main () {

    scanf("%d%d", &K, &n); ++K;

    for (int i = 1, fa; i <= n; ++i)  {

        scanf("%d%d%d", s + i, p + i, &fa);

        addEdge(fa, i);

    }

    dfs(0);

    double l = 0, r = 10000, ans;

    while (r - l >= eps) {

        double mid = (l + r) * 0.5;

        if (check(mid)) ans = mid, l = mid + eps;

        else r = mid - eps;

    }

    printf ("%.3lf\n", ans);

    return 0;

}