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

感谢

帅爷爷给我的神题。。
这题学了一下分数规划和一个特殊的DP技巧，对于这种问题，我们要是用dfs序来DP，普通的复杂度就可以从$n^2$变成n<script type="math/tex" id="MathJax-Element-32">n</script>了
真的太神辣

题解

今天比较懒，不想写了。。

可以自行取代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
const int N=2505;
int k,n;
struct qq
{int x,y,last;
}s[N];
int num=0,last[N];
int X[N],Y[N];
const double MIN=-999999999.0;
const double eps=1e-16;
void init (int x,int y)
{num++;s[num].x=x;s[num].y=y;s[num].last=last[x];last[x]=num;
}
int dfn[N],id[N],r[N],cnt=0;
void dfs (int x,int fa)
{cnt++;dfn[x]=cnt;id[cnt]=x;for (int u=last[x];u!=-1;u=s[u].last){int y=s[u].y;if (y==fa) continue;dfs(y,x);}r[x]=cnt;
}
double val[N];
double f[N][N][2];//dfs序上的第几个点 有多少个人 这个人选了没 
void DP ()
{for (int u=1;u<=cnt+1;u++)for (int i=1;i<=k+1;i++)f[u][i][0]=f[u][i][1]=MIN;f[1][1][1]=val[id[1]];for (int u=1;u<=cnt;u++)for (int i=1;i<=k+1;i++){if (f[u][i][0]!=MIN){f[u][i+1][1]=max(f[u][i][0]+val[id[u]],f[u][i+1][1]);f[r[id[u]]+1][i][0]=max(f[r[id[u]]+1][i][0],f[u][i][0]);}if (f[u][i][1]!=MIN){f[r[id[u]]+1][i][0]=max(f[r[id[u]]+1][i][0],f[u][i][1]);if (u<cnt){f[u+1][i+1][1]=max(f[u+1][i+1][1],f[u][i][1]+val[id[u+1]]);f[u+1][i][0]=max(f[u+1][i][0],f[u][i][1]);}}}
}
bool check (double x)
{for (int u=1;u<=n;u++) val[u]=Y[u]-X[u]*x;val[0]=0;DP();return f[cnt+1][k+1][0]>=-eps;
}
int main()
{num=0;memset(last,-1,sizeof(last));scanf("%d%d",&k,&n);for (int u=1;u<=n;u++){int r;scanf("%d%d%d",&X[u],&Y[u],&r);init(r,u);}dfs(0,0);//for (int u=1;u<=cnt;u++) printf("%d %d %d\n",dfn[id[u]],r[id[u]],id[u]);double L=0.0,R=10000;while (L+1e-6<=R){double mid=(L+R)/2;//printf("%lf %lf\n",L,R);if (check(mid)) L=mid;else R=mid;}printf("%.3lf\n",L);return 0;
}