[文章目录]
Description
现在我们的手头有N个软件，对于一个软件i，它要占用Wi的磁盘空间，它的价值为Vi。我们希望从中选择一些软件安装到一台磁盘容量为M计算机上，使得这些软件的价值尽可能大（即Vi的和最大）。
但是现在有个问题：软件之间存在依赖关系，即软件i只有在安装了软件j（包括软件j的直接或间接依赖）的情况下才能正确工作（软件i依赖软件j)。幸运的是，一个软件最多依赖另外一个软件。如果一个软件不能正常工作，那么它能够发挥的作用为0。
我们现在知道了软件之间的依赖关系：软件i依赖软件Di。现在请你设计出一种方案，安装价值尽量大的软件。一个软件只能被安装一次，如果一个软件没有依赖则Di=0，这时只要这个软件安装了，它就能正常工作。
形成的图是基环树森林，对于一个环只有选和不选。tarjan缩环，树上跑背包即可。时间复杂度O(n*m^2)
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 110
using namespace std;
int n,m,w[N],v[N],num,root;
int head[N],nxt[N],to[N],cnt;
inline void add(int x,int y)
{
to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt;
}
int dfn[N],low[N],bel[N],z[N],top,tot,W[N],V[N],fa[N];
bool inz[N];
void tarjan(int x)
{
dfn[x]=low[x]=++tot; z[++top]=x; inz[x]=1;
for(int i=head[x];i;i=nxt[i])
{
if(!dfn[to[i]]) tarjan(to[i]),low[x]=min(low[x],low[to[i]]);
else if(inz[to[i]]) low[x]=min(low[x],dfn[to[i]]);
}
if(low[x]==dfn[x])
{
int t; num++;
do
{
t=z[top--];
inz[t]=0;
bel[t]=num;
}while(t!=x);
}
}
int Head[N],Nxt[N],To[N],Cnt;
inline void Add(int x,int y)
{
To[++Cnt]=y; Nxt[Cnt]=Head[x]; Head[x]=Cnt;
}
int f[N][510];
void dfs(int x)
{
int i,j,k;
for(i=Head[x];i;i=Nxt[i])
{
dfs(To[i]);
for(j=m;~j;--j)
for(k=j;~k;--k)
f[x][j]=max(f[x][j],f[x][j-k]+f[To[i]][k]);
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i) scanf("%d",w+i);
for(int i=1;i<=n;++i) scanf("%d",v+i);
for(int d,i=1;i<=n;++i)
{
scanf("%d",&d);
add(d,i);
}
for(int i=0;i<=n;++i) if(!dfn[i]) tarjan(i);
root=bel[0];
for(int i=1;i<=n;++i)
{
W[bel[i]]+=w[i]; V[bel[i]]+=v[i];
for(int j=head[i];j;j=nxt[j])
if(bel[i]!=bel[to[j]])
{
Add(bel[i],bel[to[j]]);
fa[bel[to[j]]]=bel[i];
}
}
for(int i=1;i<=num;++i) if(!fa[i]&&i!=root) Add(root,i);
memset(f,0xef,sizeof f);
for(int i=1;i<=num;++i) if(W[i]<=m) f[i][W[i]]=V[i];
dfs(root); int ans=0;
for(int i=0;i<=m;++i)
ans=max(ans,f[root][i]);
printf("%d",ans);
return 0;
}