首页 > 代码库 > 洛谷 P2515 [HAOI2010]软件安装

洛谷 P2515 [HAOI2010]软件安装

题目描述

现在我们的手头有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 )

 

输出格式:

 

一个整数,代表最大价值

 

输入输出样例

输入样例#1:
3 105 5 62 3 40 1 1
输出样例#1:
5

 

 

Tarjan缩点+树形dp

屠龙宝刀点击就送

#include <ctype.h>#include <cstdio>#define N 605void read(int &x){    x=0;bool f=0;    char ch=getchar();    while(!isdigit(ch)) {if(ch==-) f=1;ch=getchar();}    while(isdigit(ch)) {x=x*10+ch-0;ch=getchar();}    x=f?(~x)+1:x;}struct node{    int next,to;}edge[N<<1];struct node2{    int next,to;}edge2[N<<1];struct thing{    int v,w;}th[N];bool in[N],instack[N];int head2[N],cnt2,f[N][N],w[N],v[N],stack[N],top,n,m,head[N],cnt,sumcol,col[N],dfn[N],low[N],tim;void add(int u,int v){    edge[++cnt].next=head[u];    edge[cnt].to=v;    head[u]=cnt;}int min(int a,int b){return a>b?b:a;}int max(int a,int b){return a>b?a:b;}void tarjan(int x){    dfn[x]=low[x]=++tim;    instack[x]=1;    stack[++top]=x;    for(int i=head[x];i;i=edge[i].next)    {        int v=edge[i].to;        if(instack[v]) low[x]=min(low[x],dfn[v]);        if(!dfn[v]) tarjan(v),low[x]=min(low[x],low[v]);    }    if(low[x]==dfn[x])    {        int t;        sumcol++;        do        {            t=stack[top--];            instack[t]=false;            col[t]=sumcol;            th[sumcol].v+=v[t];            th[sumcol].w+=w[t];        }while(t!=x);    }}void dp(int x)//此处DP为树上01背包 {    for(int i=head2[x];i;i=edge2[i].next)    {        dp(edge2[i].to);//延伸的点继续dp        for(int j=m-th[x].w;j>=0;j--)        {            for(int k=0;k<=j;k++) f[x][j]=max(f[x][j],f[x][k]+f[edge2[i].to][j-k]);        }    }    for(int j=m;j>=0;j--)    {        if(j>=th[x].w) f[x][j]=f[x][j-th[x].w]+th[x].v;        else f[x][j]=0;    }}void add2(int u,int v){    edge2[++cnt2].next=head2[u];    edge2[cnt2].to=v;    head2[u]=cnt2;}void rebuild(){    for(int i=1;i<=n;i++)    {        for(int j=head[i];j;j=edge[j].next)        {            int v=edge[j].to;            if(col[v]!=col[i])            {                in[col[v]]=1;                add2(col[i],col[v]);            }        }    }}int main(){    read(n);read(m);    for(int i=1;i<=n;i++) read(w[i]);    for(int i=1;i<=n;i++) read(v[i]);    for(int x,i=1;i<=n;i++)    {        read(x);        if(x) add(x,i);    }    for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);    rebuild();    for(int i=1;i<=sumcol;i++)    {        if(!in[i])         {            in[i]=1;            add2(sumcol+1,i);        }    }    dp(sumcol+1);    printf("%d",f[sumcol+1][m]);    return 0;}

 

洛谷 P2515 [HAOI2010]软件安装