BZOJ 4753 [Jsoi2016]最佳团体 | 树上背包分数规划

又是一道卡精度卡得我头皮发麻的题……

题面（……蜜汁改编版）

YL大哥是24OI的大哥，有一天，他想要从(N)个候选人中选(K)个小弟（(N, K le 2500))。

想要成为大哥的小弟不是件容易事，必须要有一个举荐人才行，所以每个候选人(i)都有一个另一个候选人(R_i)作为举荐人，只有当举荐人(R_i)被大哥选为小弟时，候选人(i)才有可能被选。

每个候选人都有一个选取代价(S_i)和选取收益(P_i)，请问大哥如何选取才能使单位代价的收益最大，即，使(frac{sum P_i}{sum S_i})最大？

题解

这道题也是个分数规划题！

二分答案(mid)，如果有一种选取方案使得(frac{sum P_i}{sum S_i} > mid)，即存在比mid更优的答案，那么我们找到的(frac{sum P_i}{sum S_i})最大值一定大于(mid)。所以我们把(frac{sum P_i}{sum S_i})作为权值，跑一遍树上背包。

这种树上背包（(n)个点中取(m)个，取的点的父亲必须被取）有(n^2)的做法——在dfs序（前序）上dp。(dp[i][j])表示dfs序中前(i - 1)个取(j)个的最大权值。
(dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + val[seq[i]] - mid * cost[seq[i]]);)
(dp[i + sze[seq[i]]][j] = max(dp[i + sze[seq[i]]][j], dp[i][j]);)
（seq[i]表示序列中的第i个，val是收益，cost是代价）

#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#define space putchar(' ')
#define enter putchar('
')
using namespace std;
typedef long long ll;
template <class T>
void read(T &x){
    char c;
    bool op = 0;
    while(c = getchar(), c < '0' || c > '9')
    if(c == '-') op = 1;
    x = c - '0';
    while(c = getchar(), c >= '0' && c <= '9')
    x = x * 10 + c - '0';
    if(op) x = -x;
}
template <class T>
void write(T x){
    if(x < 0) putchar('-'), x = -x;
    if(x >= 10) write(x / 10);
    putchar('0' + x % 10);
}

const int N = 2505, INF = 0x3f3f3f3f;
int n, m, val[N], cost[N], adj[N], nxt[N];
int seq[N], idx, sze[N];
double l, r = 10000, mid, dp[N][N];

void dfs(int u){
    seq[++idx] = u, sze[u] = 1;
    for(int v = adj[u]; v; v = nxt[v])
        dfs(v), sze[u] += sze[v];
}
bool check(){
    for(int i = 1; i <= idx + 1; i++)
        for(int j = 0; j <= m; j++)
            dp[i][j] = -INF;
    dp[1][0] = 0;
    for(int i = 1; i <= idx; i++)
        for(int j = 0; j <= m; j++){
            dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + val[seq[i]] - mid * cost[seq[i]]);
            dp[i + sze[seq[i]]][j] = max(dp[i + sze[seq[i]]][j], dp[i][j]);
        }
    return dp[idx + 1][m] > -1e-9;
}

int main(){

    read(m), read(n);
    m++;
    for(int i = 1, fa; i <= n; i++){
        read(cost[i]), read(val[i]), read(fa);
        nxt[i] = adj[fa], adj[fa] = i;
    }
    dfs(0);
    while(abs(r - l) > 1e-5){
        mid = (l + r) / 2;
        if(check()) l = mid;
        else r = mid;
    }
    printf("%.3lf
", (l + r) / 2);

    return 0;
}