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 1Sample 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 即可。
代码
#includeusing 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\n",mid);}int main(){ work(); return 0;}