[文章目录]
Description
JSOI信息学代表队一共有N名候选人，这些候选人从1到N编号。方便起见，JYY的编号是0号。每个候选人都由一位编号比他小的候选人Ri推荐。如果Ri=0则说明这个候选人是JYY自己看上的。为了保证团队的和谐，JYY需要保证，如果招募了候选人i，那么候选人Ri"也一定需要在团队中。当然了，JYY自己总是在团队里的。每一个候选人都有一个战斗值Pi"，也有一个招募费用Si"。JYY希望招募K个候选人（JYY自己不算），组成一个性价比最高的团队。也就是，这K个被JYY选择的候选人的总战斗值与总招募总费用的比值最大。1<=K<=N<=2500
分数规划+树形背包。复杂度O(n^2*logn)。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define R register
#define N 2600
int n,m,s[N];
int head[N],to[N],nxt[N],cnt;
inline void add(int x,int y)
{
to[++cnt]=y;
nxt[cnt]=head[x];
head[x]=cnt;
}
double f[N][N],p[N],mid;
int siz[N];
inline double Max(double x,double y){return x>y?x:y;}
void dfs(int x)
{
siz[x]=1; f[x][1]=p[x]-mid*s[x];
R int i,j,k;
for(i=head[x];i;i=nxt[i])
{
dfs(to[i]);
for(j=siz[x];j>0;--j)
for(k=siz[to[i]];k>0;--k)
f[x][j+k]=Max(f[x][j+k],f[x][j]+f[to[i]][k]);
siz[x]+=siz[to[i]];
}
}
bool check()
{
memset(f,0xef,sizeof f);
dfs(0);
return f[0][m+1]>0;
}
int main()
{
scanf("%d%d",&m,&n);
int x;
for(int i=1;i<=n;++i)
{
scanf("%d%lf%d",s+i,p+i,&x);
add(x,i);
}
double l=0,r=10000;
int tim=40;
while(tim--)
{
mid=(l+r)/2;
if(check()) l=mid;
else r=mid;
}
printf("%.3lf",l);
return 0;
}