软件安装
内存限制：128 MiB 时间限制：1000 ms 标准输入输出
题目描述
现在我们的手头有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)
输出格式
一个整数，代表最大价值。
样例
样例输入
3 10
5 5 6
2 3 4
0 1 1样例输出
5没什么好说的。
非常简单的树dp
10分算法
其实是你dp打错了才会10分。
1个注意点（由于博主沙雕打法导致的）
if(x!=0){ for(ll j=m;j>=w1[x];j--)f[x][j]=f[x][j-w1[x]]+v1[x];for(ll j=w1[x]-1;j;j--)f[x][j]=0;}
没清零！（上面给它赋值了但实施上它本来就不该有值）
40分算法
没打tarjan就会40分。
事实上当你发现你一直40wrong ans并且改不出来时就应该想想tarjan
100分
如果打了tarjan就100分了。
和某个叫「选课」的题特别像。
选课会打这个就会。
以下是本人丑陋的代码。
#include<bits/stdc++.h> #define ll long long #define A 2100 using namespace std; ll ver[A],f[A][A],fa[A],dis[A],deep[A],chatot=0,root,sum[A],w[A],d[A],v[A],num=0,top=0,ins[A],sta[A],dfn[A],low[A],cnt=0,scc[110][110],belong[A]; ll head2[A],head[A],nxt[A],nxt2[A],ver2[A],tot2=0,tot=0,du[A],v1[A],w1[A]; bool flag[A],vis[A]; ll n,m,k,t,xx,yy,zz; inline ll read(){ll f=1,x=0;char ch=getchar();while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;} inline void add(ll x,ll y){fa[y]=x,ver[++tot]=y,nxt[tot]=head[x],head[x]=tot;} inline void add2(ll x,ll y){ver2[++tot2]=y,nxt2[tot2]=head2[x],head2[x]=tot2;} inline void rebuilt() {for(ll i=1;i<=n;i++){for(ll j=head[i];j;j=nxt[j]){ll y=ver[j];if(belong[y]!=belong[i])add2(belong[i],belong[y]),du[belong[y]]++;}} } inline ll tarjan(ll x) {dfn[x]=low[x]=++num;sta[++top]=x;ins[x]=1;for(ll i=head[x];i;i=nxt[i]){ll y=ver[i];if(dfn[y]==0){tarjan(y);low[x]=min(low[x],low[y]);}else if(ins[y])low[x]=min(low[x],dfn[y]);}if(dfn[x]==low[x]){++cnt;ll yy=0;while(1){yy=sta[top--];ins[yy]=0; belong[yy]=cnt;v1[cnt]+=v[yy];w1[cnt]+=w[yy];if(yy==x)break;}} } void dfs(ll x) {f[x][0]=0;for(ll i=head2[x];i;i=nxt2[i]){ll y=ver2[i];dfs(y);for(ll j=m;j>=0;j--)for(ll k=j;k>=0;k--)f[x][j]=max(f[x][j],f[x][j-k]+f[y][k]);}if(x!=0){ for(ll j=m;j>=w1[x];j--)f[x][j]=f[x][j-w1[x]]+v1[x];for(ll j=w1[x]-1;j;j--)f[x][j]=0;} } int main() {n=read(),m=read();for(ll i=1;i<=n;i++)w[i]=read();for(ll i=1;i<=n;i++)v[i]=read();for(ll i=1;i<=n;i++){d[i]=read();add(d[i],i);}for(ll i=1;i<=n;i++)if(!dfn[i]) tarjan(i);rebuilt();for(ll i=1;i<=cnt;i++){if(!du[i])add2(0,i);}dfs(0);cout<<f[0][m]<<endl; }
