Description
JSOI信息学代表队一共有N名候选人，这些候选人从1到N编号。方便起见，JYY的编号是0号。
每个候选人都由一位编号比他小的候选人Ri推荐。如果Ri=0则说明这个候选人是JYY自己看上的。
为了保证团队的和谐，JYY需要保证，如果招募了候选人i，那么候选人Ri"也一定需要在团队中。
当然了，JYY自己总是在团队里的。每一个候选人都有一个战斗值Pi"，也有一个招募费用Si"。
JYY希望招募K个候选人（JYY自己不算），组成一个性价比最高的团队。
也就是，这K个被JYY选择的候选人的总战斗值与总招募总费用的比值最大。
Input
输入一行包含两个正整数K和N。
接下来N行，其中第i行包含3个整数Si,Pi,Ri表示候选人i的招募费用，战斗值和推荐人编号。
对于100%的数据满足1≤K≤N≤2500,0<"Si,Pi"≤10^4,0≤Ri<i
Output
输出一行一个实数，表示最佳比值。答案保留三位小数。
Sample Input
1 2
1000 1 0
1 1000 1
Sample Output
0.001
Solution
通过题目,我们要想到一下几点:
- 要求的是比值,01分数规划。
- 由于要求一个单独的最优解,于是二分。
- 用背包的思想来转移DP。
二分答案 (now), 则其满足不等式 $$sum_{i}{k}p_i*now>=sum_{i}{k}s_i$$
此时每个点对于答案的贡献即为: (p_i*now-s_i)
于是我们便可以对答案进行转移。
定义状态: (f[i][j]) 表示当前到了 DFS 序为 (i) 的节点,已经选了 (j) 个成员是的最大价值.
状态转移: 由于树形依赖关系,我们每一个节点转移有两种方向:
- (f[i+1][j+1]) 即选择这个点(同时之后有机会选择这个点的子树)。
- (f[i+siz[i]][j+1]) 即不选择这个点以及它的子树,此时直接转移到(siz[i])之后。
然后就是 DFS+二分+DP 即可。
代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=2508;
const double eps=0.00001;
struct sj{
int to;
int next;
}a[maxn];
int head[maxn],size;
void add(int x,int y)
{
a[++size].to=y;
a[size].next=head[x];
head[x]=size;
}
int n,k,cnt;
double w[maxn],z[maxn];
int pos[maxn],siz[maxn],id[maxn];
void dfs(int x)
{
siz[x]=1; pos[x]=++cnt;id[cnt]=x;
for(int i=head[x];i;i=a[i].next)
{int tt=a[i].to;
dfs(tt); siz[x]+=siz[tt];}
}
double f[maxn][maxn];
double val[maxn];
void dp(double mid)
{
for(int i=1;i<=n;i++) val[pos[i]]=z[i]-mid*w[i];
for(int i=1;i<=n+1;i++)
for(int j=0;j<=k+1;j++) f[i][j]=-1e18;
for(int i=0;i<=n;i++)
{int mm=min(i,k+1);
for(int j=0;j<=mm;j++)
{
if (f[i][j]+val[i]>f[i+1][j+1])
f[i+1][j+1]=f[i][j]+val[i];
if (f[i][j]>f[i+siz[id[i]]][j])
f[i+siz[id[i]]][j]=f[i][j];
}
}
}
int ans;
void work()
{
cin>>k>>n;
for(int i=1;i<=n;i++)
{
int fr;
scanf("%lf%lf%d",&w[i],&z[i],&fr);
add(fr,i);
}
cnt=-1;
dfs(0);
double mid,l=eps,r=9500;
while (r-l>eps)
{
mid=(l+r)/2;
dp(mid);
if (f[n+1][k+1]>=0) l=mid;
else r=mid;
}
printf("%.3lf
",mid);
}
int main()
{
work();
return 0;
}