题目
题目描述
原题
JSOI信息学代表队一共有N名候选人，这些候选人从1到N编号
方便起见，JYY的编号是0号
每个候选人都由一位编号比他小的候选人Ri推荐。如果Ri=0则说明这个候选人是JYY自己看上的
为了保证团队的和谐，JYY需要保证，如果招募了候选人i，那么候选人Ri也一定需要在团队中
当然了，JYY自己总是在团队里的。每一个候选人都有一个战斗值Pi，也有一个招募费用Si
JYY希望招募K个候选人（JYY自己不算），组成一个性价比最高的团队
也就是，这K个被JYY选择的候选人的总战斗值与总招募总费用的比值最大
输入格式
输入一行包含两个正整数K和N
接下来N行，其中第i行包含3个整数Si,Pi,Ri表示候选人i的招募费用，战斗值和推荐人编号
输出格式
输出一行一个实数，表示最佳比值，答案保留三位小数
样例
样例输入
样例输出
数据范围与提示
对于100%的数据满足1⩽K⩽N⩽2500,0<Si,Pi⩽104,0⩽Ri<i
题解
题意就是选一个大小为k的连通块，使得这个连通块的总战斗值与总招募费用的比值最大
因为要求的是最大值，所以可以采用二分答案（实数二分！实数二分！实数二分！），所以只需要考虑如何检验这个性价比是否可达到
这个检验就是一个树形DP，我们用fi,j表示根为i的子树中选j个人的相当于最高性价比减去二分的性价比的量（因为为了避免精度差，计算的不是两个数真正的差，而是01分数规划后的结果），递推的部分就是一个常规的树形DP的递推了
值得注意的是，最后的答案是f0,k+1，不是f0,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
| #include<algorithm>
#include<cstdio>
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);
}
|