题面
0/1分数规划+树形背包检查
要求$\frac{\sum P_i}{\sum S_i}的最大值，$按照0/1分数规划的做法，二分一个mid之后把式子化成$\sum P_i=\sum S_i*mid$。然后相当于每个点$i$的点权是$P_i-S_i*mid$来做树形背包。
然而我并不太会树形背包=。=
设$dp[i][j]$表示以$i$为根的子树中选出$j$个物品的最优解，然后转移的时候 枚举子树->枚举已经合并好的部分->枚举一棵新子树 来转移
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 const int N=2550; 6 const double inf=1e9; 7 int p[N],noww[N],goal[N],siz[N]; 8 double pwr[N],cst[N],val[N],dp[N][N]; ?9 int n,k,rd,cnt;10 double l,r,mid,ans;11 void link(int f,int t)12 {13 ????noww[++cnt]=p[f];14 ????goal[cnt]=t,p[f]=cnt;15 }16 void mark(int nde)17 {18 ????siz[nde]=1;19 ????for(int i=p[nde];i;i=noww[i]) ???20 ????????mark(goal[i]),siz[nde]+=siz[goal[i]];21 }22 void DFS(int nde)23 {24 ????int size=0,mini=0;25 ????for(int i=0;i<=k;i++) dp[nde][i]=-inf;26 ????if(nde) dp[nde][1]=val[nde],size++,mini++;27 ????else dp[nde][0]=0;28 ????for(int i=p[nde];i;i=noww[i])29 ????{30 ????????DFS(goal[i]);31 ????????for(int j=size;j>=mini;j--)32 ????????????for(int k=1;k<=siz[goal[i]];k++)33 ????????????????dp[nde][j+k]=max(dp[nde][j+k],dp[nde][j]+dp[goal[i]][k]);34 ????????size+=siz[goal[i]];35 ????}36 }37 int main()38 {39 ????register int i,j;40 ????scanf("%d%d",&k,&n);41 ????for(i=1;i<=n;i++)42 ????{43 ????????scanf("%lf%lf%d",&cst[i],&pwr[i],&rd);44 ????????link(rd,i),r=max(r,(double)pwr[i]);45 ????}46 ????mark(0);47 ????for(i=1;i<=30;i++)48 ????{49 ????????mid=(l+r)/2; 50 ????????for(j=1;j<=n;j++)51 ????????????val[j]=pwr[j]-mid*cst[j];52 ????????DFS(0); (dp[0][k]<0)?r=mid:l=mid; 53 ????}54 ????printf("%.3lf",l);55 ????return 0;56 }解题：JSOI 2016 最佳团体
原文地址：https://www.cnblogs.com/ydnhaha/p/9808309.html