本文共 1925 字，大约阅读时间需要 6 分钟。

软件安装

Description

现在我们的手头有N个软件，对于一个软件i，它要占用Wi的磁盘空间，它的价值为Vi。我们希望从中选择一些软件安装到一台磁盘容量为M计算机上，使得这些软件的价值尽可能大（即Vi的和最大）。

但是现在有个问题：软件之间存在依赖关系，即软件i只有在安装了软件j（包括软件j的直接或间接依赖）的情况下才能正确工作（软件i依赖软件j)。幸运的是，一个软件最多依赖另外一个软件。如果一个软件不能正常工作，那么它能够发挥的作用为0。

我们现在知道了软件之间的依赖关系：软件i依赖软件Di。现在请你设计出一种方案，安装价值尽量大的软件。一个软件只能被安装一次，如果一个软件没有依赖则Di=0，这时只要这个软件安装了，它就能正常工作。

Input

第1行：N, M (0<=N<=100, 0<=M<=500)

Output

第1行：一个整数，代表最大价值。

Sample Input

3 105 5 62 3 40 1 1

Sample Output

5

解题思路

我们先缩点，再反制，再DP

#include
   
    #include
    
     using namespace std;int n,m,totn,totw,a[1100][1100];int w[1100],v[1100],b[1100],c[1100];int fa[1100],f[1100][5100];void floyed(){   	for(int i=1;i<=n;i++)		for(int j=1;j<=n;j++)			for(int k=1;k<=n;k++)				if(a[k][i]==1&&a[i][j]==1)					a[k][j]=1;}void merge(){   	totn=n;	for(int i=1;i<=totn;i++)		for(int j=1;j<=totn;j++)		{   			if(a[i][j]==1&&a[j][i]==1&&w[i]>0&&w[j]>0&&i!=j)			{   				totn++;				w[totn]=w[i]+w[j];				v[totn]=v[i]+v[j];				totw--;				w[i]=totw,w[j]=totw;			}			if(a[fa[j]][j]==1&&a[j][fa[j]]==1&&w[fa[j]]<0&&w[j]>0)			{   				w[n-w[fa[j]]]+=w[j];				v[n-w[fa[j]]]+=v[j];				w[j]=w[fa[j]];			}			if(w[fa[j]]<0&&w[j]>0)				if((a[fa[j]][j]==1&&a[j][fa[j]]==0)||(a[fa[j]][j]==0&&a[j][fa[j]]==1))					fa[j]=n-w[fa[j]];		}}int dfs(int x,int k){   	if(f[x][k]>0)		return f[x][k];	if(x==0||k<=0)		return 0;	f[b[x]][k]=dfs(b[x],k);	f[x][k]=f[b[x]][k];	int y=k-w[x];	for(int i=0;i<=y;i++)	{   		f[c[x]][y-i]=dfs(c[x],y-i);		f[b[x]][i]=dfs(b[x],i);		f[x][k]=max(f[x][k],v[x]+f[c[x]][y-i]+f[b[x]][i]);	}	return f[x][k];}int main(){   	cin>>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 i=1;i<=n;i++)	{   		scanf("%d",&fa[i]);		a[fa[i]][i]=1;	}	floyed();	merge();	for(int i=1;i<=totn;i++)		if(w[i]>0)		{   			b[i]=c[fa[i]];			c[fa[i]]=i;		}	cout<
     
      <