题目描述
现在我们的手头有NNN个软件，对于一个软件i，它要占用WiW_iWi的磁盘空间，它的价值为ViV_iVi。我们希望从中选择一些软件安装到一台磁盘容量为MMM计算机上，使得这些软件的价值尽可能大（即ViV_iVi的和最大）。
但是现在有个问题：软件之间存在依赖关系，即软件i只有在安装了软件jjj（包括软件j的直接或间接依赖）的情况下才能正确工作（软件iii依赖软件jjj)。幸运的是，一个软件最多依赖另外一个软件。如果一个软件不能正常工作，那么它能够发挥的作用为000。
我们现在知道了软件之间的依赖关系：软件i依赖软件DiD_iDi。现在请你设计出一种方案，安装价值尽量大的软件。一个软件只能被安装一次，如果一个软件没有依赖则Di=0D_i=0Di=0，这时只要这个软件安装了，它就能正常工作。
输入输出格式
输入格式：第1行：N,M(0≤N≤100,0≤M≤500)N,M(0leq Nleq 100, 0leq Mleq 500)N,M(0≤N≤100,0≤M≤500)
第2行：W1,W2,...Wi,...,Wn(0≤Wi≤M)W_1,W_2, ... W_i, ..., W_n (0leq W_ileq M)W1,W2,...Wi,...,Wn(0≤Wi≤M)
第3行：V1,V2,...,Vi,...,Vn(0≤Vi≤1000)V_1, V_2, ..., V_i, ..., V_n (0leq V_ileq 1000)V1,V2,...,Vi,...,Vn(0≤Vi≤1000)
第4行：D1,D2,...,Di,...,Dn(0≤Di≤N,Di≠i)D_1, D_2, ..., D_i, ..., D_n (0leq D_ileq N, D_i≠i)D1,D2,...,Di,...,Dn(0≤Di≤N,Di≠i)
输出格式：一个整数，代表最大价值
输入输出样例
3 10
5 5 6
2 3 4
0 1 1
5
开始想得是在已经完缩点的树上，遍历出所有的背包组合可能，然后进行普通的背包dp
后来发现不可行，1：一个若见只能安装一次，组合之间可能有并集。2：时间复杂读可能会太高：
发现只需要进行树形dp即可：
f[ i ,j] 表示在以i为根的子树内，话费j的磁盘空间 所能带来的最大价值
有一点就是，进行树上背包的时候，默认的必须选根节点的软件，否则后面的无法满足依赖。
具体看代码吧：
注释掉的dfs是另一种的默认选取根节点的做法，不让根节点参与dp，最后在后面的在加上，最重要的小于根节点的j，dp[i,j]要设为0！！！！！
没有注释的也是一种方法，就是空出来cost[i] 这麽多容量
1 #include<cstdio>
2 #include<cstring>
3 #include<cmath>
4 #include<cstdlib>
5 #include<climits>
6 #include<ctime>
7 #include<algorithm>
8 #include<complex>
9 #include<iostream>
10 #include<map>
11 #include<queue>
12 #include<vector>
13 #define INF 0x3f3f3f3f
14 #define ll long long
15 using namespace std;
16 struct edge
17 {
18 int to,next;
19 }a[1010],dag[1010];
20 int hag[1010];
21 int head[1010];
22 int v[1010];
23 int w[1010];
24 int cost[1010];
25 int val[1010];
26 int f[1010][5050];
27 int low[1010];
28 int dfn[1010];
29 int now(0);
30 int hep[1010];
31 int top(0);
32 int vis[1010];
33 int fa[1010];
34 int up[1010];
35 int usd[1010];
36 int cnt(0);
37 int cal(0);
38 int tot(0);
39 int n,m;
40 void addedge(int xi,int yi)
41 {
42 a[cnt].to=yi;
43 a[cnt].next=head[xi];
44 head[xi]=cnt++;
45 }
46 void addag(int xi,int yi)
47 {
48 dag[cal].to=yi;
49 dag[cal].next=hag[xi];
50 hag[xi]=cal++;
51 }
52 void tarjan(int u)
53 {
54 low[u]=dfn[u]=++now;
55 hep[++top]=u;vis[u]=1;
56 for(int i=head[u];i!=-1;i=a[i].next)
57 {
58 int v=a[i].to;
59 if(!dfn[v])
60 {
61 tarjan(v);
62 low[u]=min(low[u],low[v]);
63 }
64 else if(vis[v])low[u]=min(low[u],dfn[v]);
65 }
66 if(dfn[u]==low[u])
67 {
68 ++tot;
69 vis[u]=0;
70 while(hep[top+1]!=u)
71 {
72 fa[hep[top]]=tot;
73 vis[hep[top--]]=0;
74 }
75 }
76 }
77
78
79 /*
80 void dfs(int u)
81 {
82 //for(int i=cost[u];i<=m;i++)f[u][i]=val[u];
83 for(int i=hag[u];i!=-1;i=dag[i].next)
84 {
85 int v=dag[i].to;
86 dfs(v);
87 for(int j=m-cost[u];j>=0;j--)
88 {
89 for(int q=0;q<=j;q++)
90 {
91 f[u][j]=max(f[u][j],f[u][j-q]+f[v][q]);
92 }
93 }
94 }
95
96 for (int i=m;i-cost[u]>=0;i--)
f[u][i]=f[u][i-cost[u]]+val[u];
for (int i=0;i<cost[u];i++)f[u][i]=0;
97
98
99 }*/
100
101
102
103 void dfs(int u)
104 {
105 for(int i=cost[u];i<=m;i++)f[u][i]=val[u];
106 for(int i=hag[u];i!=-1;i=dag[i].next)
107 {
108 int v=dag[i].to;
109 dfs(v);
110 for(int j=m-cost[u];j>=0;j--)
111 {
112 for(int q=0;q<=j;q++)
113 {
114 f[u][j+cost[u]]=max(f[u][j+cost[u]],f[u][j+cost[u]-q]+f[v][q]);
115 }
116 }
117 }
118 }
119
120 int main()
121 {
122 memset(head,-1,sizeof(head));
123 memset(hag,-1,sizeof(hag));
124 scanf("%d%d",&n,&m);
125 for(int i=1;i<=n;i++)scanf("%d",&w[i]);
126 for(int i=1;i<=n;i++)scanf("%d",&v[i]);
127 for(int i=1;i<=n;i++)
128 {
129 int x;
130 scanf("%d",&x);
131 up[i]=x;
132 if(x!=0)addedge(x,i);
133 }
134 for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i);
135 for(int i=1;i<=n;i++)
136 {
137 val[fa[i]]+=v[i];cost[fa[i]]+=w[i];
138 if(fa[i]!=fa[up[i]]&&up[i]!=0)
139 {
140 addag(fa[up[i]],fa[i]);
141 usd[fa[i]]++;
142 }
143 }
144 int s=tot+1;
145 for(int i=1;i<=tot;i++)if(!usd[i])addag(s,i);
146 cost[s]=0;val[s]=0;
147 dfs(s);
148 printf("%d",f[s][m+cost[s]]);
149 return 0;
150 }