bzoj4753: [Jsoi2016]最佳团体（分数规划+树形依赖背包）

旧城等待， 2021-10-01 01:42 310阅读 0赞

菜菜推荐的“水题”虐了我一天T T...（菜菜好强强qwq~

显然是个分数规划题，二分答案算出p\[i\]-mid\*s\[i\]之后在树上跑依赖背包，选k个最大值如果>0说明还有更优解。

第一次接触树形依赖背包，所以之前写的十几发WA和TLE都是错误写法，我还是naive啊T T

树形依赖背包的普遍做法是按dfs序DP，设f\[i\]\[j\]为dfs序为i的点，已经选了j个点的最大价值，nxt\[i\]为i的下一个子树的dfs序则有：

f\[nxt\[i\]\]\[j\]=f\[i\]\[j\]

f\[i+1\]\[j+1\]=f\[i\]\[j\]+w\[i\]

注意树形依赖背包最好使用刷表法，因为如果要求代价必须为k并且权值有负数的话使用填表法可能会导致从不合法状态转移。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<iostream> 
    #include<cstring>
    #include<cstdlib>
    #include<cstdio>
    #include<cmath> 
    #include<algorithm> 
    using namespace std;
    const int maxn=2510,inf=1e9;
    struct poi{
         int too,pre;}e[maxn];
    int n,k,x,tot,cnt,mx;
    int dfn[maxn],nxt[maxn],last[maxn],s[maxn],p[maxn];
    double f[maxn][maxn],w[maxn];
    inline void read(int &k)
    {
        int f=1;k=0;char c=getchar();
        while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar();
        while(c<='9'&&c>='0')k=k*10+c-'0',c=getchar();
        k*=f;
    }
    void add(int x,int y){e[++tot].too=y;e[tot].pre=last[x];last[x]=tot;}
    void dfs(int x)
    {
        dfn[x]=cnt++;
        for(int i=last[x];i;i=e[i].pre)dfs(e[i].too);
        nxt[dfn[x]]=cnt;
    }
    int main()
    {
        read(k);read(n);
        for(int i=1;i<=n;i++)read(s[i]),read(p[i]),read(x),add(x,i),mx=max(mx,p[i]);
        dfs(0);
        double l=0,r=1e4;
        while(r-l>1e-5)
        {
            double mid=(l+r)/2;
            for(int i=1;i<=n;i++)w[dfn[i]]=1.0*p[i]-mid*s[i];
            for(int i=1;i<=n+1;i++)for(int j=0;j<=k+1;j++)f[i][j]=-inf;
            for(int i=0;i<=n;i++)
            for(int j=0;j<=min(i,k+1);j++)
            {
                if(f[i][j]>f[nxt[i]][j])f[nxt[i]][j]=f[i][j];
                if(f[i][j]+w[i]>f[i+1][j+1])f[i+1][j+1]=f[i][j]+w[i];
            }
            if(f[n+1][k+1]>1e-5)l=mid;else r=mid;
        }
        printf("%.3lf\n",l);
    }

第二种做法仅能在代价为选取点数的情况下使用，直接在树上做背包，但是在对于每一个子节点做完背包之后才把子节点的size加进父节点，这样的复杂度也是O(N^2)的。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<iostream>
    #include<cstring>
    #include<cstdlib>
    #include<cstdio>
    using namespace std;
    const int maxn=2510;
    double eps=1e-5,inf=1e12;
    struct poi{
         int too,pre;}e[maxn];
    int n,k,x,tot,sum;
    int p[maxn],s[maxn],size[maxn],last[maxn];
    double f[maxn][maxn],w[maxn],g[maxn];
    void read(int &k)
    {
        int f=1;k=0;char c=getchar();
        while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar();
        while(c<='9'&&c>='0')k=k*10+c-'0',c=getchar();
        k*=f;
    }
    void add(int x,int y){e[++tot].too=y;e[tot].pre=last[x];last[x]=tot;}
    void dfs(int x)
    {
        size[x]=1;f[x][1]=w[x];
        for(int i=last[x];i;i=e[i].pre)
        {
            dfs(e[i].too);
            for(int j=0;j<=size[x]+size[e[i].too];j++)g[j]=f[x][j];
            for(int j=1;j<=size[x];j++)
            for(int k=1;k<=size[e[i].too];k++)
            g[j+k]=max(g[j+k],f[x][j]+f[e[i].too][k]); 
            size[x]+=size[e[i].too];
            for(int j=1;j<=size[x];j++)f[x][j]=g[j];
        }
    }   
    int main()
    {
        read(k);read(n);
        for(int i=1;i<=n;i++)read(s[i]),read(p[i]),read(x),add(x,i);
        double l=0,r=1e4;
        while(r-l>eps)
        {
            double mid=(l+r)/2;
            for(int i=1;i<=n;i++)w[i]=1.0*p[i]-mid*s[i];
            for(int i=0;i<=n;i++)for(int j=1;j<=k+1;j++)f[i][j]=-inf;
            dfs(0);if(f[0][k+1]>eps)l=mid;else r=mid;
        }
        printf("%.3lf\n",l);
    }

转载于:https://www.cnblogs.com/Sakits/p/7690778.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20210724/50b02ba201b34c5980bc4e677e2c294d.png