BZOJ4753：[JSOI2016]最佳团体—

BZOJ4753：[JSOI2016]最佳团体——题解

阅读量：5815 次

发布时间：2019-06-18

本文共 1783 字，大约阅读时间需要 5 分钟。

JSOI信息学代表队一共有N名候选人，这些候选人从1到N编号。方便起见，JYY的编号是0号。每个候选人都由一位

编号比他小的候选人Ri推荐。如果Ri=0则说明这个候选人是JYY自己看上的。为了保证团队的和谐，JYY需要保证，

如果招募了候选人i，那么候选人Ri"也一定需要在团队中。当然了，JYY自己总是在团队里的。每一个候选人都有

一个战斗值Pi"，也有一个招募费用Si"。JYY希望招募K个候选人（JYY自己不算），组成一个性价比最高的团队。

也就是，这K个被JYY选择的候选人的总战斗值与总招募总费用的比值最大。

01分数规划裸题，二分答案w，每个点点权为p[i]-w*s[i]，判断最大值是否>0即可。

显然是树型背包问题，由于看不懂什么神奇的刷表法，我还是写的复杂度我不会证的dfs。

于是我人傻自带大常数硬生生把傻逼题写成神题……

#include#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                using namespace std;typedef long long ll;typedef double dl;const int INF=1e7;const int N=2505;inline int read(){ int X=0,w=0;char ch=0; while(!isdigit(ch)){w|=ch=='-';ch=getchar();} while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar(); return w?-X:X;}struct node{ int to,nxt;}e[N*2];int cnt,k,n,s[N],p[N],head[N],sz[N];dl dp[N][N],w[N];inline int add(int u,int v){ e[++cnt].to=v;e[cnt].nxt=head[u];head[u]=cnt;}void dfs(int u){ for(int i=0;i<=k;i++)dp[u][i]=-INF; if(u)dp[u][1]=w[u],sz[u]=1; else dp[u][0]=0,sz[u]=0; for(int i=head[u];i;i=e[i].nxt){ int v=e[i].to;dfs(v); int len=u?1:0; for(int j=min(k,sz[u]);j>=len;j--) for(int l=1;l<=min(k-j,sz[v]);l++) dp[u][j+l]=max(dp[u][j+l],dp[u][j]+dp[v][l]); sz[u]+=sz[v]; }}bool pan(dl W){ for(int i=1;i<=n;i++)w[i]=(dl)p[i]-W*s[i]; dfs(0); return dp[0][k]>0;}int main(){ k=read(),n=read(); for(int i=1;i<=n;i++){ s[i]=read(),p[i]=read(); add(read(),i); } dl l=0,r=1e4; for(int i=1;i<=30;i++){ dl mid=(l+r)/2; if(pan(mid))l=mid; else r=mid; } printf("%.3lf\n",l); return 0;}