[JSOI 2016] 最佳团体

[题目链接]

https://www.lydsy.com/JudgeOnline/problem.php?id=4753

[算法]

很明显的分数规划

可以用树形动态规划（树形背包）检验答案

时间复杂度 ： O(N^3logN)

[代码]

#include<bits/stdc++.h>

using namespace std;

#define MAXN 2510

const double eps = 1e-;

const double inf = 1e9;

int n , tot , k;

int head[MAXN],a[MAXN],b[MAXN],size[MAXN],father[MAXN];

double f[MAXN][MAXN];

double value[MAXN],tmp[MAXN];

struct edge

{

        int to , nxt;

} e[MAXN];

template <typename T> inline void chkmax(T &x,T y) { x = max(x,y); }

template <typename T> inline void chkmin(T &x,T y) { x = min(x,y); }

template <typename T> inline void read(T &x)

{

    T f = ; x = ;

    char c = getchar();

    for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;

    for (; isdigit(c); c = getchar()) x = (x << ) + (x << ) + c - '';

    x *= f;

}

inline void dp(int u)

{

        size[u] = ;

        f[u][] = ;

        f[u][] = value[u];

        for (int i = head[u]; i; i = e[i].nxt)

        {

                int v = e[i].to;

                dp(v);

                for (int j = ; j <= size[u] + size[v]; j++) tmp[j] = -inf;

                for (int j = ; j <= size[u]; j++)

                {

                        for (int k = ; k <= size[v]; k++)

                        {

                                chkmax(tmp[j + k],f[u][j] + f[v][k]);

                        }

                }

                for (int j = ; j <= size[u] + size[v]; j++) f[u][j] = tmp[j];

                size[u] += size[v];

        }

}

inline void addedge(int u,int v)

{

        tot++;

        e[tot] = (edge){v,head[u]};

        head[u] = tot;

}

inline bool check(double mid)

{

        for (int i = ; i <= n; i++) value[i] = (double)1.0 * b[i] - (double)1.0 * mid * a[i];

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

        {

                for (int j = ; j <= n + ; j++)

                {

                        f[i][j] = -inf;

                }

        }

        dp();

        return f[][k + ] >= eps;

}

int main()

{

        read(k); read(n);

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

        {

                read(a[i]);

                read(b[i]);

                read(father[i]);

                addedge(father[i],i);

        }

        double l =  , r =  , ans;

        while (l + eps < r)

        {

                double mid = (l + r) / 2.0;

                if (check(mid))

                {

                        l = mid;

                        ans = mid;

                } else r = mid;

        }

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

        return ;

}