2481: 信息学奥赛一本通T1576-选课

解题思路:

注意事项:

参考代码:

#include<bits/stdc++.h>
using namespace std;
struct node
{
	int to;
	int w;
	int next;
}mp[100005];
int head[100005];
int cnt=0;
void add(int a,int b)
{
	mp[++cnt].to=b;
	mp[cnt].next=head[a];
	head[a]=cnt;
}
int a[100005];
int dp[305][305];
int n,m;
void dfs(int u)
{
	for(int i=head[u];i;i=mp[i].next)
	{
		int v;
		v=mp[i].to;	
		dfs(v);
		for(int j=m+1;j>0;j--)
		{
			for(int k=0;k<j;k++)
			{
				dp[u][j]=max(dp[u][j],dp[u][j-k]+dp[v][k]);
			}			
		}
	}	
}
int main()
{
	
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		int b;
		cin>>b>>dp[i][1];
		add(b,i);
	}
	dfs(0);
	cout<<dp[0][m+1];
	return 0;
}