首页 > 代码库 > 洛谷 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]软件安装
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。