[洛谷P4322][题解][JSOI2016]最佳团体
0.？？？
似乎又咕咕咕了好久呢……开了学时间少了（绝不是因为我懒哦）
又刷到了一个有趣的新算法（or新解法？），特此写一写~
1.概述
给出一棵树和每个点的\(S_i,P_i\)，只能从根节点向下连续选点，求\(\max\{\frac{\sum{P_i}}{\sum{S_i}}\}\)。
2.解法
运用到了一种叫做分数规划的解法（虽然听起来很高端其实简单得不能再简单系列）。首先，我们发现答案中的比值太难看了，去除！于是就变成了：\(\max\{\sum{(P_i-ans\times S_i)}\}\)。暂且将求和号里面的东西记作\(val_i\)，然后根据\(ans\)的不同答案也会有不同的取值（当前答案小了还是大了会体现在\(\sum{val_i}\ge 0\)或\(<0\)，可以自己推一下），这启发我们二分答案。
总结一下：
1.将答案变换形式，更易于求解；
2.二分答案+判断。
之后再往二分里面套一个普通的\(DP\)，设\(f[i][j]\)为\(i\)子树中选\(j\)个点的最大答案，转移就是依次枚举每个儿子选的个数。
3.代码
缺省源在里
#define N 2510
int k,n,siz[N];
double val[N],f[N][N],s[N],p[N];
struct Edge {
int to,nxt;
}e[N<<1];
int head[N],cnt;
inline void ade(int u,int v){
e[++cnt].to=v;
e[cnt].nxt=head[u];
head[u]=cnt;
}
void DFS(int now){
f[now][1]=val[now],siz[now]=1;
for(rg int i=head[now];i;i=e[i].nxt){
int v=e[i].to;
DFS(v);
siz[now]+=siz[v];
for(rg int j=min(siz[now],k+1);j;j--){
for(rg int l=0;l<=min(siz[now],j-1);l++){
f[now][j]=max(f[now][j],f[v][l]+f[now][j-l]);
}
}
}
}
bool Check(double mid){
for(rg int i=1;i<=n;i++){
val[i]=p[i]-mid*s[i];
}
for(rg int i=0;i<=n;i++){
for(rg int j=1;j<=k+1;j++)f[i][j]=-INF;
}
DFS(0);
return f[0][k+1]>=0;
}
int main(){
Read(k),Read(n);
for(rg int i=1;i<=n;i++){
int rr;
scanf("%lf%lf%d",&s[i],&p[i],&rr);
ade(rr,i);
}
double l=0.0,r=10000.0,mid;
while(r-l>eps){
mid=(l+r)/2;
if(Check(mid))l=mid;
else r=mid;
}
printf("%.3lf\n",l);
return 0;
}