题目
题目描述
原题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选择的候选人的总战斗值与总招募总费用的比值最大
输入格式
输入一行包含两个正整数$K$和$N$
接下来$N$行，其中第$i$行包含$3$个整数$S_i,P_i,R_i$表示候选人i的招募费用，战斗值和推荐人编号
输出格式
输出一行一个实数，表示最佳比值，答案保留三位小数
样例
样例输入
1 | 1 2 |
样例输出
1 | 0.001 |
数据范围与提示
对于$100\%$的数据满足$1\leqslant K\leqslant N\leqslant 2500,0<S_i,P_i\leqslant 10^4,0\leqslant R_i<i$
题解
题意就是选一个大小为$k$的连通块，使得这个连通块的总战斗值与总招募费用的比值最大
因为要求的是最大值，所以可以采用二分答案（实数二分！实数二分！实数二分！），所以只需要考虑如何检验这个性价比是否可达到
这个检验就是一个树形DP，我们用$f_{i,j}$表示根为i的子树中选$j$个人的相当于最高性价比减去二分的性价比的量（因为为了避免精度差，计算的不是两个数真正的差，而是01分数规划后的结果），递推的部分就是一个常规的树形DP的递推了
值得注意的是，最后的答案是$f_{0,k+1}$，不是$f_{0,k}$
附上代码：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
using namespace std;
int n,k,tot,s[2510],p[2510],r[2510],head[2510],nxt[2510],to[2510],size[2510];
double L,R=1e4,mid,eps=1e-5,f[2510][2510],F[2510];
void add(int x)
{
nxt[++tot]=head[r[x]],head[r[x]]=tot,to[tot]=x;
}
void dfs(int x)
{
size[x]=1,f[x][1]=p[x]-s[x]*mid;
for(int i=head[x];i;i=nxt[i]){
dfs(to[i]);
for(int j=1;j<=size[x]+size[to[i]];j++) F[j]=-1e9;
for(int j=1;j<=size[x];j++) for(int k=0;k<=size[to[i]];k++) F[j+k]=max(F[j+k],f[x][j]+f[to[i]][k]);
for(int j=1;j<=size[x]+size[to[i]];j++) f[x][j]=F[j];
size[x]+=size[to[i]];
}
}
int pd()
{
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) f[i][j]=-1e9;
dfs(0);
return f[0][k+1]<=0;
}
int main()
{
scanf("%d%d",&k,&n);
for(int i=1;i<=n;i++) scanf("%d%d%d",&s[i],&p[i],&r[i]),add(i);
while(L+eps<R){
mid=(L+R)/2.0;
if(pd()) R=mid;
else L=mid+eps;
}
printf("%.3lf",L);
}