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

标签：题解

阅读体验

BZOJ题目链接 洛谷题目链接

具体实现

看到分数和最值，考虑分数规划

我们要求的是一个\(\dfrac{\sum P_i}{\sum S_i}\)最大对吧，考虑二分一个答案\(mid\)

那么就会有合法条件\(\dfrac{\sum P_i}{\sum S_i}\ge mid\)，化简一下：\(\sum{(P_i-S_i×mid)}\ge 0\)

所以每次二分一个\(mid\)之后得到一个新数组v[i]=P[i]-S[i]×mid，我们跑背包\(check\)它最后是否大于等于\(0\)就可以了，因为有约束条件，所以把树建出来跑树上背包

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

等一下！

这个\(dp\)的转移看上去向\(n^2\)的啊，再乘上\(Dfs\)的\(n\)的复杂度不就复杂度假了吗

其实不然，总体来看，每一对节点的\(dp\)状态只会在他们的\(Lca\)处被转移一次，想一想为什么（我想了挺久），所以复杂度就是\(n^2\)的啦

然而它还是卡常啊，最后\(Junlier\)就卡了很久，终于\(988ms\)卡过去了。。。

代码

#include<bits/stdc++.h>

#define il inline

#define rg register

#define ldb double

#define lst long long

#define rgt register int

#define N 2550

#define pb push_back

#define qw G[now][i]

using namespace std;

const lst Inf=1e18;

const ldb eps=1e-4;

il int read()

{

    int s=0,m=0;char ch=getchar();

    while(!isdigit(ch)){if(ch=='-')m=1;ch=getchar();}

    while( isdigit(ch))s=(s<<3)+(s<<1)+(ch^48),ch=getchar();

    return m?-s:s;

}

int K,n,Dex;

int siz[N];

struct LJL{int S,P,fa;}ljl[N];

ldb v[N],tmp[N],dp[N][N],Ans;

vector<int> G[N];

il void Merge(rgt x,rgt y)

{

    for(rgt i=0;i<=K+1;++i)tmp[i]=-Inf;

    for(rgt i=1,up;i<=siz[x];++i)

    {

        up=min(K+1-i,siz[y]);

        for(rgt j=1;j<=up;++j)

            tmp[i+j]=max(tmp[i+j],dp[y][j]+dp[x][i]);

    }for(rgt i=0;i<=K+1;++i)dp[x][i]=max(dp[x][i],tmp[i]);

}

void Dfs(rgt now)

{

    for(rgt j=0;j<=K+1;++j)dp[now][j]=-Inf;

    dp[now][1]=v[now],siz[now]=1;

    for(rgt i=0;i<G[now].size();++i)

        Dfs(qw),Merge(now,qw),siz[now]+=siz[qw];

}

il bool check(ldb lim)

{

    for(rgt i=1;i<=n;++i)

        v[i]=ljl[i].P-ljl[i].S*lim;

    Dfs(0);return dp[0][K+1]>=0;

}

int main()

{

    K=read(),n=read();

    for(rgt i=1;i<=n;++i)

    {

        ljl[i]=(LJL){read(),read(),read()};

        G[ljl[i].fa].pb(i);

    }ldb le=eps,ri=1e5,mid;

    while(ri-le>eps)

    {

        mid=(le+ri)/2;

        if(check(mid))Ans=mid,le=mid+eps;

        else ri=mid-eps;

    }return printf("%.3lf\n",Ans),0;

}