题目描述
现在我们的手头有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 10 5 5 6 2 3 4 0 1 1
输出样例#1:
5
题解:
容易知道如果形成了环,那么这个环要么选要么不选,所以直接tarjan缩点,价值容量合并即可.
然后建好新图之后直接树上背包即可,注意是拿子节点做多重背包,而且父节点强制要选
最后虚拟一个根节点,然后直接向所有子树连边即可 答案在新点上
1 #include <algorithm> 2 #include <iostream> 3 #include <cstdlib> 4 #include <cstring> 5 #include <cstdio> 6 #include <cmath> 7 #define RG register 8 #define il inline 9 using namespace std; 10 const int N=105,M=505; 11 int head[N],num=0,nxt[N],to[N],du[N]; 12 int n,m,w[N],val[N]; 13 void init(int x,int y){ 14 nxt[++num]=head[x];to[num]=y;head[x]=num; 15 } 16 int dfn[N],low[N],DFN=0,st[N],top=0,sum=0,bel[N],fa[N],S,V[N],W[N];bool vis[N],inst[N],d[N][N]; 17 void tarjan(int x){ 18 int u,v; 19 dfn[x]=low[x]=++DFN; 20 st[++top]=x;vis[x]=true;inst[x]=true; 21 for(int i=head[x];i;i=nxt[i]){ 22 u=to[i]; 23 if(!dfn[u]){ 24 tarjan(u); 25 low[x]=min(low[x],low[u]); 26 } 27 else if(inst[u])low[x]=min(low[x],dfn[u]); 28 } 29 if(dfn[x]==low[x]){ 30 sum++; 31 do{ 32 v=st[top--]; 33 bel[v]=sum;inst[v]=false; 34 }while(v!=x && top); 35 } 36 } 37 struct node{ 38 int to,next; 39 }e[N<<1]; 40 int NUM=0,Head[N],f[N][M]; 41 void addedge(int x,int y){ 42 e[++NUM].next=Head[x];e[NUM].to=y;Head[x]=NUM; 43 } 44 void dfs(int x){ 45 int u; 46 f[x][w[x]]=val[x]; 47 for(int i=Head[x];i;i=e[i].next){ 48 u=e[i].to; 49 dfs(u); 50 for(int j=m-w[x];j>=0;j--){ 51 for(int k=0;k<=j;k++){ 52 if(j+w[x]-k>=0) 53 f[x][j+w[x]]=max(f[x][j+w[x]],f[x][j+w[x]-k]+f[u][k]); 54 } 55 } 56 57 } 58 } 59 void work() 60 { 61 scanf("%d%d",&n,&m);S=n+1; 62 for(int i=1;i<=n;i++)scanf("%d",&W[i]); 63 for(int i=1;i<=n;i++)scanf("%d",&V[i]); 64 for(int i=1;i<=n;i++){ 65 scanf("%d",&fa[i]); 66 if(fa[i])init(fa[i],i); 67 } 68 for(int i=1;i<=n;i++) 69 if(!vis[i])tarjan(i); 70 for(int i=1;i<=n;i++){ 71 val[bel[i]]+=V[i],w[bel[i]]+=W[i]; 72 } 73 for(int i=1;i<=n;i++){ 74 if(fa[i]==0)continue; 75 if(bel[i]==bel[fa[i]])continue; 76 if(!d[bel[i]][bel[fa[i]]]){ 77 addedge(bel[fa[i]],bel[i]); 78 d[bel[i]][bel[fa[i]]]=true; 79 d[bel[fa[i]]][bel[i]]=true; 80 du[bel[i]]++; 81 } 82 } 83 for(int i=1;i<=n;i++){ 84 if(du[bel[i]]==0){ 85 addedge(S,bel[i]); 86 du[bel[i]]=-1; 87 } 88 } 89 dfs(S); 90 printf("%d ",f[S][m]); 91 } 92 93 int main() 94 { 95 work(); 96 return 0; 97 }