[关闭]
@Junlier 2018-10-18T23:06:05.000000Z 字数 1641 阅读 1615

BZOJ4753: [Jsoi2016]最佳团体(分数规划+树上背包)

题解
阅读体验
BZOJ题目链接 洛谷题目链接

具体实现

看到分数和最值,考虑分数规划
我们要求的是一个最大对吧,考虑二分一个答案
那么就会有合法条件,化简一下:
所以每次二分一个之后得到一个新数组v[i]=P[i]-S[i]×mid,我们跑背包它最后是否大于等于就可以了,因为有约束条件,所以把树建出来跑树上背包

dp[i][j]表示节点选了个凑出的的最大值,我们最后就只要判断dp[0][K+1]>=0就可以啦

等一下!
这个的转移看上去向的啊,再乘上的复杂度不就复杂度假了吗
其实不然,总体来看,每一对节点的状态只会在他们的处被转移一次,想一想为什么(我想了挺久),所以复杂度就是的啦
然而它还是卡常啊,最后就卡了很久,终于卡过去了。。。

代码

  1. #include<bits/stdc++.h>
  2. #define il inline
  3. #define rg register
  4. #define ldb double
  5. #define lst long long
  6. #define rgt register int
  7. #define N 2550
  8. #define pb push_back
  9. #define qw G[now][i]
  10. using namespace std;
  11. const lst Inf=1e18;
  12. const ldb eps=1e-4;
  13. il int read()
  14. {
  15. int s=0,m=0;char ch=getchar();
  16. while(!isdigit(ch)){if(ch=='-')m=1;ch=getchar();}
  17. while( isdigit(ch))s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
  18. return m?-s:s;
  19. }
  20. int K,n,Dex;
  21. int siz[N];
  22. struct LJL{int S,P,fa;}ljl[N];
  23. ldb v[N],tmp[N],dp[N][N],Ans;
  24. vector<int> G[N];
  25. il void Merge(rgt x,rgt y)
  26. {
  27. for(rgt i=0;i<=K+1;++i)tmp[i]=-Inf;
  28. for(rgt i=1,up;i<=siz[x];++i)
  29. {
  30. up=min(K+1-i,siz[y]);
  31. for(rgt j=1;j<=up;++j)
  32. tmp[i+j]=max(tmp[i+j],dp[y][j]+dp[x][i]);
  33. }for(rgt i=0;i<=K+1;++i)dp[x][i]=max(dp[x][i],tmp[i]);
  34. }
  35. void Dfs(rgt now)
  36. {
  37. for(rgt j=0;j<=K+1;++j)dp[now][j]=-Inf;
  38. dp[now][1]=v[now],siz[now]=1;
  39. for(rgt i=0;i<G[now].size();++i)
  40. Dfs(qw),Merge(now,qw),siz[now]+=siz[qw];
  41. }
  42. il bool check(ldb lim)
  43. {
  44. for(rgt i=1;i<=n;++i)
  45. v[i]=ljl[i].P-ljl[i].S*lim;
  46. Dfs(0);return dp[0][K+1]>=0;
  47. }
  48. int main()
  49. {
  50. K=read(),n=read();
  51. for(rgt i=1;i<=n;++i)
  52. {
  53. ljl[i]=(LJL){read(),read(),read()};
  54. G[ljl[i].fa].pb(i);
  55. }ldb le=eps,ri=1e5,mid;
  56. while(ri-le>eps)
  57. {
  58. mid=(le+ri)/2;
  59. if(check(mid))Ans=mid,le=mid+eps;
  60. else ri=mid-eps;
  61. }return printf("%.3lf\n",Ans),0;
  62. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注