「JSOI 2016」最佳团体

Description

题目链接:BZOJ 4753

有 $N$ 名候选人,从 $1$ 到 $N$ 编号,队长编号为 $0$,每个候选人都由一位编号比他小的候选人推荐(如果为 $0$ 则表示是队长推荐的)。队长希望招募 $K$ 个人,但是他需要保证:如果招募了 $x$,那么他的推荐人也要招募(队长总是在团队里的)。每个人都有代价 $C_i$ 和价值 $W_i$ 两个值,招募可以获得的价值为 $\frac{\sum W_i}{\sum C_i}$,你需要最大化这个值,答案保留 $3$ 位小数。

数据范围:$1\le K\le N\le 2500$,$1\le C_i,W_i\le 10^4$


Solution

先做一个小转化:以 $0$ 为根节点,选择 $K+1$ 个点,其中根节点必须选择。

首先我们考虑树形 $\text{DP}$,显然是一道普通的树上背包问题。但是由于答案是一个比值,无法记录状态进行转移,所以我们引入 $01$ 分数规划

这个式子显然是可以二分答案的,因此可以得到

由于分母是正数,我们将式子拆开

可得

故我们可以二分答案 $x$,将问题转化为:每个点有 $1$ 个属性 $P_i=W_i-x\times C_i$,能否使选取的点的属性和大于等于 $0$。

设计状态:$f[i][j]$ 表示在以第 $i$ 个节点为根的子树中,选择 $j$ 个节点的最大属性和。

$\text{DP}$ 为朴素的树上背包问题,转移非常显然(注意根节点 $i$ 对应的 $j$ 至少为 $1$,我就因为这个调试了半天)。

注意初始化:$f[i][0]=0$,$f[i][1]=W_i-x\times C_i$,其余状态的值均为无穷小。

时间复杂度:$O(N^2)​$(复杂度证明见 「HAOI 2015」树上染色


Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N=2505;
const double eps=1e-5;
int n,m,tot,c[N],s[N],hd[N],sz[N];
double w[N],f[N][N];
struct Edge{
int to,nxt;
}e[N];

void add(int u,int v) {
e[++tot].to=v;
e[tot].nxt=hd[u];
hd[u]=tot;
}
void dfs(int x) {
sz[x]=1; f[x][1]=w[x];
for(int i=hd[x];i;i=e[i].nxt) {
int v=e[i].to; dfs(v);
for(int j=sz[x];j>=1;--j)
for(int k=0;k<=sz[v];++k)
f[x][j+k]=max(f[x][j+k],f[x][j]+f[v][k]);
sz[x]+=sz[v];
}
}
bool check(double x) {
memset(f,-10,sizeof(f));
for(int i=0;i<=n;++i) f[i][0]=0;
for(int i=1;i<=n;++i) w[i]=(double)s[i]-x*c[i];
dfs(0);
return f[0][m]>=0;
}
int main() {
scanf("%d%d",&m,&n); ++m;
for(int fa,i=1;i<=n;++i) {
scanf("%d%d%d",&c[i],&s[i],&fa);
add(fa,i);
}
double l=0,r=1e4,ans=0;
while(l+eps<=r) {
double mid=(l+r)/2;
if(check(mid)) ans=mid,l=mid+eps; else r=mid-eps;
}
printf("%.3lf\n",ans);
return 0;
}
0%