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

时间:2022-02-17 14:30:22

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('\n')
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\n", (l + r) / 2); return 0;
}