Description

JSOI 信息学代表队一共有 \(n\) 名候选人, 这些候选人从 \(1\) 到 \(n\) 编号. 方便起见, JYY 的编号是 \(0\) 号. 每个候选人都由一位编号比他小的候选人 \(R_i\) 推荐. 如果 \(R_i=0\) 则说明这个候选人是 JYY 自己看上的.

为了保证团队的和谐, JYY 需要保证, 如果招募了候选人 \(i\), 那么候选人 \(R_i\) 也一定需要在团队中. 当然了, JYY 自己总是在团队里的. 每一个候选人都有一个战斗值 \(P_i\), 也有一个招募费用 \(S_i\). JYY 希望招募 \(K\) 个候选人 (JYY 自己不算), 组成一个性价比最高的团队.

也就是, 这 \(K\) 个被 JYY 选择的候选人的总战斗值与总招募总费用的比值最大.

Input

输入一行包含两个正整数 \(K\) 和 \(n\).

接下来 \(n\) 行, 其中第 \(i\) 行包含 \(3\) 个整数 \(S_i, P_i, R_i\) 表示候选人 \(i\) 的招募费用, 战斗值和推荐人编号.

Output

输出一行一个实数, 表示最佳比值. 答案保留三位小数.

Sample Input

1 2
1000 1 0
1 1000 1

Sample Output

0.001

Data Range

对于 100% 的数据, 满足:\(1 \leq K \leq n \leq 2500, 0 \leq S_i, P_i \leq 10^4, 0 \leq R_i \lt i\).

Explanation

属于 \(0-1\) 分数规划问题, 题目要求的是最大化:\[ \begin{aligned} & ans = \frac{\sum_{i=1}^{n} P_i}{\sum_{i=1}^{n} S_i}\\ & \forall i \in ans, R_i \in ans \end{aligned} \] 需要二分 \(ans\) 的值, 使得这个玩意儿可以用 \(0-1\) 背包来解决.

我们成功把一个奇怪的问题转化成了树上背包......

另外注意精度问题.

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cmath>

using namespace std;
typedef long long lli;
typedef double llf;
const int maxn = 2510, maxm = 5010;
const llf epsilon = 1e-8;
const llf infinit = 1e9;

struct edge
{
    int u, v;
    edge *next;
};

int root, ecnt;
edge *edges[maxn], epool[maxm];
int par[maxn];
void set_child(int u, int v)
{
    edge *p = &epool[++ecnt];
    p->u = u; p->v = v;
    p->next = edges[u]; edges[u] = p;
    par[v] = u;
    return ;
}

int m, n;
int a[maxn], b[maxn]; // Required calculation of b/a
int siz[maxn];
llf v[maxn], f[maxn][maxn], g[maxn];

void build(llf x)
{
    for (int i = 0; i <= n; i++) {
        v[i] = a[i] - x * b[i];
        for (int j = 0; j <= n; j++)
            f[i][j] = -infinit;
    }
    return ;
}
void update(int x, int y)
{
    // Tempoorary array: g[]
    for (int i = 0; i <= siz[x] + siz[y]; i++)
        g[i] = -infinit;
    for (int i = 0; i <= siz[x]; i++)
        for (int j = 0; j <= siz[y]; j++)
            g[i+j] = max(g[i+j], f[x][i] + f[y][j]);
    siz[x] += siz[y];
    for (int i = 0; i <= siz[x]; i++)
        f[x][i] = max(f[x][i], g[i]);
    return ;
}
void dfs(int x)
{
    siz[x] = 0;
    f[x][0] = 0;
    for (edge *ep = edges[x]; ep; ep = ep->next) {
        dfs(ep->v);
        update(x, ep->v);
    }
    for (int i = siz[x]; i >= 0; i--)
        f[x][i+1] = f[x][i] + v[x];
    siz[x] += 1;
    f[x][0] = 0;
    return ;
}

int main(int argc, char** argv)
{
    scanf("%d%d", &m, &n);
    m += 1; // Himself
    for (int i = 1, x; i <= n; i++) {
        scanf("%d%d%d", &b[i], &a[i], &x);
        set_child(x, i);
    }
    // Binary search for results?
    llf res = 0.0, l = 0.0, r = 10000.0;
    while (fabs(r - l) > epsilon) {
        llf mid = (l + r) / 2;
        build(mid);
        dfs(0);
        if (f[0][m] > 0) {
            res = mid;
            l = mid;
        } else {
            r = mid;
        }
    }
    // Result
    printf("%.3lf\n", res);
    return 0;
}