【题解】[Jsoi2016] 最佳团体 bzoj4753 ——quhengyi11

题目：

我是可爱的传送门酱 (ˉ▽￣～)

题解：

这道题还算比较简单

显然分数规划，要 $\exists\frac{\sum p_i}{\sum s_i}\geq k$最大化 k，也就是 $\exists \sum p_i – k\times s_i \geq 0$, 每次二分一下改变点权，然后跑树背包就行。

设 $f[u][i]$表示 u 点为子树 i 个选中，为了满足依赖关系，我们将初始状态设为 $f[u][1]=p[u]-k\times s[u]$即可，不需要设 $f[u][0]=0$否则转移会出错。

代码：

#include<bits/stdc++.h> 
#define fo(i, a, b) for (int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (int i = (a); i >= (b); --i)
#define edge(i, u) for (int i = head[u], v = e[i].v; i; i = e[i].nxt, v = e[i].v)
#define N 2505
#define pb push_back
#define F first
#define S second
#define ll long long
#define inf 1000000007
#define mp std::make_pair
#define lowbit(x) (x & -x)
#define ls (k << 1)
#define rs (k << 1 | 1)
#define mod 998244353
#define up 10000
#define eps 1e-4
int n, m;
int S[N], P[N], fa[N];
double f[N][N], g[N];
std::vector<int> s[N];
double mid;
int sz[N];
inline void dfs (int u)
{
    sz[u] = 1;
    f[u][1] = P[u] - mid * S[u];
    int size = s[u].size() - 1;
    fo (I, 0, size)
    {
        int v = s[u][I];
        dfs(v);
        memset(g, 0xf3, sizeof g);
        fo (i, 0, sz[u])
            fo (j, 0, sz[v])
                g[i + j] = std::max(g[i + j], f[u][i] + f[v][j]);
        sz[u] += sz[v];
        fo (i, 0, sz[u])
            f[u][i] = std::max(f[u][i], g[i]);
    }
}
inline bool check ()
{
    memset(f, 0xf3, sizeof f);
    dfs(0);
    return f[0][m] >= 0;
}
int main ()
{
    scanf("%d %d", &m, &n);
    ++m;
    fo (i, 1, n)
    {
        scanf("%d %d %d", &S[i], &P[i], &fa[i]);
        s[fa[i]].pb(i);
    }
    double l = 0, r = 10000;
    while (l + eps < r)
    {
        mid = (l + r) / 2;
        if (check())
            l = mid;
        else
            r = mid;
    }
    printf("%.3lf", l);
    return 0;
}