图论杂题T9
传送门
现在我们的手头有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)
一个整数，代表最大价值。
taijan+树上dp
每个点只有一个依赖父节点，那么显然是个树
但每个主件可能有多级的附件，这可能成环，所以用到了tarjan缩点
30%算法（当然可以多骗一个点拿到40分）
首先不考虑环，对于树上dp，
首先考虑在所有主件前加上一个 “ 超级主件” 0
我们将它变成一个dfs序的序列（dfs序为“根左右”的先根遍历）
（我是用 ord[]记录每个树上的节点的编号，ord[1]是0节点，ord[n+1]是n节点）
然后，考虑状态定义
f[i][j]为从i到n背包容量为j时的最大价值
转移：如果考虑购买i，则由f[i+1] （i 的儿子或兄弟）转移过来 即 f[i+1][j-cost[i]]+value[i]
如果不购买i，则其子树都不能买，那么就由f[i+sum[i]]（sum[i]为i的子树 包括i 的节点个数）转移过来 即f[i+sum[i]][j]
所以状态转移方程为
f[i][j]=max{f[i+1][j-cost[i]]+value[i],f[i+sum[i]][j]}
先dfs预处理sum和dfs序
然后dp，输出f[1][m]即可
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 using namespace std; 6 7 int n,m,c[305],val[305]; 8 int ord[305],f[305][505],sum[305],v[305]; 9 struct node{ 10 int v,nxt; 11 }e[305];int nu,h[305]; 12 void add(int x,int y) 13 { 14 e[++nu].v=y; 15 e[nu].nxt=h[x]; 16 h[x]=nu; 17 } 18 void dfs(int x) 19 { 20 v[x]=1; 21 ord[++ord[0]]=x; 22 for(int i=h[x];i;i=e[i].nxt) 23 { 24 int y=e[i].v; 25 if(v[y]) continue; 26 dfs(y); 27 sum[x]+=sum[y]; 28 } 29 // cout<<x<<":"<<sum[x]<<endl; 30 } 31 int main() 32 { 33 scanf("%d%d",&n,&m); 34 for(int i=1;i<=n;i++) 35 scanf("%d",&c[i]); 36 for(int i=1;i<=n;i++) 37 scanf("%d",&val[i]); 38 for(int i=1;i<=n;i++) 39 { 40 sum[i]=1; 41 int y; 42 scanf("%d",&y); 43 add(y,i); 44 } 45 dfs(0); 46 // for(int i=1;i<=n+1;i++) 47 // cout<<ord[i]<<" "; 48 for(int i=n+1;i>=1;i--) 49 { 50 for(int j=1;j<=m;j++) 51 { 52 int x=ord[i];//cout<<x<<" "; 53 f[i][j]=f[i+sum[x]][j]; 54 if(j>=c[x]) 55 f[i][j]=max(f[i][j],f[i+1][j-c[x]]+val[x]); 56 } 57 } 58 //for(int i=1;i<=m;i++) 59 printf("%d",f[1][m]); 60 } View Code
100%算法
只要先用tarjan缩点，先缩点，再加入超级主件0，然后dfs
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<vector> 6 using namespace std; 7 8 int n,m,cc[305],vall[305]; 9 int c[305],val[305]; 10 int ord[305],f[305][505],sum[305],ind[305]; 11 struct nodee{ 12 int v,nxt; 13 }ee[305];int nuu,hh[305]; 14 void addd(int x,int y) 15 { 16 ee[++nuu].v=y; 17 ee[nuu].nxt=hh[x]; 18 hh[x]=nuu; 19 } 20 struct node{ 21 int v,nxt; 22 }e[305];int nu,h[305]; 23 void add(int x,int y) 24 { 25 e[++nu].v=y; 26 e[nu].nxt=h[x]; 27 h[x]=nu; 28 } 29 void dfs(int x) 30 { 31 ord[++ord[0]]=x; 32 for(int i=h[x];i;i=e[i].nxt) 33 { 34 int y=e[i].v; 35 dfs(y); 36 sum[x]+=sum[y]; 37 } 38 } 39 int num,dfn[305],low[305]; 40 int top,st[305],ins[305]; 41 int bl[305],cnt; 42 vector <int> scc[305]; 43 void tarjan(int x) 44 { 45 dfn[x]=low[x]=++num; 46 st[++top]=x,ins[x]=1; 47 for(int i=hh[x];i;i=ee[i].nxt) 48 { 49 int y=ee[i].v; 50 if(!dfn[y]) 51 { 52 tarjan(y); 53 low[x]=min(low[x],low[y]); 54 } 55 else if(ins[y]) 56 low[x]=min(low[x],dfn[y]); 57 } 58 if(dfn[x]==low[x]) 59 { 60 int y;cnt++; 61 do 62 { 63 y=st[top--],ins[y]=0; 64 scc[cnt].push_back(y),bl[y]=cnt; 65 c[cnt]+=cc[y],val[cnt]+=vall[y]; 66 }while(x!=y); 67 } 68 } 69 void suodian() 70 { 71 for(int x=1;x<=n;x++) 72 { 73 for(int i=hh[x];i;i=ee[i].nxt) 74 { 75 int y=ee[i].v; 76 if(bl[x]!=bl[y]) 77 add(bl[x],bl[y]),ind[bl[y]]++; 78 } 79 } 80 for(int i=1;i<=cnt;i++) 81 { 82 if(!ind[i]) add(0,i); 83 sum[i]=1; 84 } 85 sum[0]=1; 86 } 87 int main() 88 { 89 scanf("%d%d",&n,&m); 90 for(int i=1;i<=n;i++) 91 scanf("%d",&cc[i]); 92 for(int i=1;i<=n;i++) 93 scanf("%d",&vall[i]); 94 for(int i=1;i<=n;i++) 95 { 96 int y; 97 scanf("%d",&y); 98 addd(y,i); 99 } 100 for(int i=1;i<=n;i++) 101 if(!dfn[i]) 102 tarjan(i); 103 suodian(); 104 dfs(0); 105 for(int i=cnt+1;i>=1;i--) 106 { 107 for(int j=1;j<=m;j++) 108 { 109 int x=ord[i]; 110 f[i][j]=f[i+sum[x]][j]; 111 if(j>=c[x]) 112 f[i][j]=max(f[i][j],f[i+1][j-c[x]]+val[x]); 113 } 114 } 115 printf("%d",f[1][m]); 116 } View Code
转载于:https://www.cnblogs.com/casun547/p/11174192.html
相关资源：kernel general block框架