软件安装

题目传送门

解题思路

1：这题可能形成环
所以要缩点，用强连通分量

void sd()//缩点
{
   	
	o=n;
	for(int i=1;i<=o;i++)
     for(int j=1;j<=o;j++)
	 {
   
		if(a[i][j]==1&&a[j][i]==1&&w[i]>0&&w[j]>0&&i!=j)
		{
   
			o++;
			w[o]=w[i]+w[j];
			v[o]=v[i]+v[j];
			w[i]=w[j]=--o1;
		}
		if(a[d[j]][j]==1&&a[j][d[j]]==1&&w[d[j]]<0&&w[j]>0)
		{
   
			w[n-w[d[j]]]+=w[j];
			v[n-w[d[j]]]+=v[j];
			w[j]=w[d[j]];
		}
		if(w[d[j]]<0&&w[j]>0)
		 if((a[d[j]][j]==1&&a[j][d[j]]==0)||(a[d[j]][j]==0&&a[j][d[j]]==1))
		 d[j]=n-w[d[j]];
	}
}

2：状态转移
我们分析x和它儿子和它爸爸的关系
它要在它爸爸选了之后才能选，所以它爸爸的值可以传承到它身上，当作不选它
我们类似完全背包的做法，枚举当前还剩的空间

		f[c[x]][k-w[x]-i]=dp(c[x], k-w[x]-i);//枚举儿子
		f[b[x]][i]=dp(b[x], i);//父亲的传承
		f[x][k]=max(f[x][k],v[x]+f[c[x]][k-w[x]-i]+f[b[x]][i]);

最后呈上AC代码

AC代码

#include<cstdio>
#include<iostream>
using namespace std;
int n,m,o,o1,w[1005],v[1005],d[1005],b[1005],c[1005],a[1005][1005],f[1005][1005];
void sd()//缩点
{
   	
	o=n;
	for(int i=1;i<=o;i++)
     for(int j=1;j<=o;j++)
	 {
   
		if(a[i][j]==1&&a[j][i]==1&&w[i]>0&&w[j]>0&&i!=j)
		{
   
			o++;
			w[o]=w[i]+w[j];
			v[o]=v[i]+v[j];
			w[i]=w[j]=--o1;
		}
		if(a[d[j]][j]==1&&a[j][d[j]]==1&&w[d[j]]<0&&w[j]>0)
		{
   
			w[n-w[d[j]]]+=w[j];
			v[n-w[d[j]]]+=v[j];
			w[j]=w[d[j]];
		}
		if(w[d[j]]<0&&w[j]>0)
		 if((a[d[j]][j]==1&&a[j][d[j]]==0)||(a[d[j]][j]==0&&a[j][d[j]]==1))
		 d[j]=n-w[d[j]];
	}
}
int dp(int x,int k)
{
   
	if(f[x][k]>0)return f[x][k];
	if(x==0||k<=0)return 0;
	f[b[x]][k]=dp(b[x], k);
	f[x][k]=f[b[x]][k];
	for(int i=0;i<=k-w[x];i++)
	{
   
		f[c[x]][k-w[x]-i]=dp(c[x], k-w[x]-i);//枚举儿子
		f[b[x]][i]=dp(b[x], i);//父亲的传承
		f[x][k]=max(f[x][k],v[x]+f[c[x]][k-w[x]-i]+f[b[x]][i]);
	}
	return f[x][k];
}
int main()
{
   
	cin>>n>>m;//输入
	for(int i=1;i<=n;i++)cin>>w[i];
	for(int i=1;i<=n;i++)cin>>v[i];
	for(int i=1;i<=n;i++)
	{
   
		cin>>d[i];
		a[d[i]][i]=1;//邻接矩阵
	}
	for(int i=1;i<=n;i++)//floyed 来缩点
	 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;
	sd();//缩点
	for(int i=1;i<=o;i++)//预处理
	 if(w[i]>0)
	 {
   
	 	b[i]=c[d[i]];
	 	c[d[i]]=i;
	 }   
	cout<<dp(c[0],m); //dp输出
}

谢谢