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

f[i][j]表示i的子树，供j个家庭看比赛的最大收入，然后初始状态也就是每个子节点（家庭）都是他们支付的金额，以及供应0个家庭的收入为0，状态转移就是分组背包的思想，每个子节点可以选择供应1个/2个/.../k个，最后统计最大值即可

答案就是第一个f[1][i]>0的i的值，i倒序枚举，因为要求最大值

代码

有一点读入叶子节点的费用时，注意下标的问题！

#include
   
    using namespace std;const int maxn=3005;int n,m,cnt,cost[maxn],f[maxn][maxn],head[maxn];struct edge{	int to,v,nxt;}G[maxn];void add(int x,int y,int z){	G[++cnt].to=y; G[cnt].nxt=head[x]; G[cnt].v=z; head[x]=cnt;}int dfs(int x){	if(x>n-m)	{		f[x][1]=cost[x];		return 1;		}		int sum=0,temp;	for(int i=head[x];i;i=G[i].nxt)	{		int to=G[i].to;		int v=G[i].v;		temp=dfs(to); sum+=temp;		for(int j=sum;j>=1;j--)			for(int z=1;z<=temp,j-z>=0;z++)				f[x][j]=max(f[x][j],f[x][j-z]+f[to][z]-v);	}	return sum;}int main(){	freopen("a.in","r",stdin);	scanf("%d%d",&n,&m);	int t,x,y;	for(int i=1;i<=n-m;i++)	{		scanf("%d",&t);		for(int j=1;j<=t;j++)		{			scanf("%d%d",&x,&y);			add(i,x,y);		}	}	for(int i=1;i<=m;i++) scanf("%d",&cost[n-m+i]);	memset(f,~0x3f,sizeof(f));	for(int i=1;i<=n;i++) f[i][0]=0;	dfs(1);	int ans;	for(int i=m;i>=0;i--) 		if(f[1][i]>=0)		{			ans=i;			break;		} 	printf("%d\n",ans);	return 0;}
   

转载地址：http://sbwm.baihongyu.com/