软件安装

内存限制：128 MiB 时间限制：1000 ms 标准输入输出

题目描述

现在我们的手头有N个软件，对于一个软件i，它要占用Wi的磁盘空间，它的价值为Vi。我们希望从中选择一些软件安装到一台磁盘容量为M计算机上，使得这些软件的价值尽可能大(即Vi的和最大)。

但是现在有个问题：软件之间存在依赖关系，即软件i只有在安装了软件j(包括软件j的直接或间接依赖)的情况下才能正确工作(软件i依赖软件j)。幸运的是，一个软件最多依赖另外一个软件。如果一个软件不能正常工作，那么它能够发挥的作用为0。

我们现在知道了软件之间的依赖关系：软件i依赖软件Di。现在请你设计出一种方案，安装价值尽量大的软件。一个软件只能被安装一次，如果一个软件没有依赖则Di=0，这时只要这个软件安装了，它就能正常工作。

输入格式

第1行：N，M (0<=N<=100．0<=M<=500)

第2行：W1，W2，…，Wi，…，Wn(0<=Wi<=M)

第3行：V1，V2，…，Vi，…，Vn(0<=Vi<=1000)

第4行：D1，D2，…，Di，…，Dn(0<=Di<=N，Di≠i)

输出格式

一个整数，代表最大价值。

样例

样例输入

样例输出

没什么好说的。

非常简单的树dp

10分算法

其实是你dp打错了才会10分。

1个注意点（由于博主沙雕打法导致的）

    if(x!=0)

    {

        for(ll j=m;j>=w1[x];j--)

            f[x][j]=f[x][j-w1[x]]+v1[x];

        for(ll j=w1[x]-1;j;j--)

            f[x][j]=0;

    }

没清零！（上面给它赋值了但实施上它本来就不该有值）

40分算法

没打tarjan就会40分。

事实上当你发现你一直40wrong ans并且改不出来时就应该想想tarjan

100分

如果打了tarjan就100分了。

和某个叫「选课」的题特别像。

选课会打这个就会。

以下是本人丑陋的代码。

#include<bits/stdc++.h>

#define ll long long

#define A 2100

using namespace std;

ll ver[A],f[A][A],fa[A],dis[A],deep[A],chatot=0,root,sum[A],w[A],d[A],v[A],num=0,top=0,ins[A],sta[A],dfn[A],low[A],cnt=0,scc[110][110],belong[A];

ll head2[A],head[A],nxt[A],nxt2[A],ver2[A],tot2=0,tot=0,du[A],v1[A],w1[A];

bool flag[A],vis[A];

ll n,m,k,t,xx,yy,zz;

inline ll read(){ll f=1,x=0;char ch=getchar();while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}

inline void add(ll x,ll y){fa[y]=x,ver[++tot]=y,nxt[tot]=head[x],head[x]=tot;}

inline void add2(ll x,ll y){ver2[++tot2]=y,nxt2[tot2]=head2[x],head2[x]=tot2;}

inline void rebuilt()

{

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

    {

        for(ll j=head[i];j;j=nxt[j])

        {

            ll y=ver[j];

            if(belong[y]!=belong[i])

                add2(belong[i],belong[y]),du[belong[y]]++;

        }

    }

}

inline ll tarjan(ll x)

{

    dfn[x]=low[x]=++num;

    sta[++top]=x;ins[x]=1;

    for(ll i=head[x];i;i=nxt[i])

    {

        ll y=ver[i];

        if(dfn[y]==0)

        {

            tarjan(y);

            low[x]=min(low[x],low[y]);

        }

        else if(ins[y])

            low[x]=min(low[x],dfn[y]);

    }

    if(dfn[x]==low[x])

    {

        ++cnt;

        ll yy=0;

        while(1)

        {

            yy=sta[top--];

            ins[yy]=0;

            belong[yy]=cnt;

            v1[cnt]+=v[yy];

            w1[cnt]+=w[yy];

            if(yy==x)

                break;

        }

    }

}

void dfs(ll x)

{

    f[x][0]=0;

    for(ll i=head2[x];i;i=nxt2[i])

    {

        ll y=ver2[i];

        dfs(y);

        for(ll j=m;j>=0;j--)

            for(ll k=j;k>=0;k--)

                f[x][j]=max(f[x][j],f[x][j-k]+f[y][k]);

    }

    if(x!=0)

    {

        for(ll j=m;j>=w1[x];j--)

            f[x][j]=f[x][j-w1[x]]+v1[x];

        for(ll j=w1[x]-1;j;j--)

            f[x][j]=0;

    }

}

int main()

{

    n=read(),m=read();

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

        w[i]=read();

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

        v[i]=read();

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

    {

        d[i]=read();

        add(d[i],i);

    }

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

        if(!dfn[i]) tarjan(i);

    rebuilt();

    for(ll i=1;i<=cnt;i++)

    {

        if(!du[i])

            add2(0,i);

    }

    dfs(0);

    cout<<f[0][m]<<endl;

}

巴特西

bzoj2427 软件安装！树dp

软件安装

题目描述

输入格式

输出格式

样例

样例输入

样例输出

最新文章

热门文章

巴特西

bzoj2427 软件安装！ 树dp

软件安装

题目描述

输入格式

输出格式

样例

样例输入

样例输出

最新文章

热门文章

bzoj2427 软件安装！树dp