luogu P2014 [CTSC1997]选课 书上背包dp+强连通分量，缩点

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=310;
int n,m;
int h[N],e[N],ne[N],idx;
int w[N];
int f[N][N];
void add(int a,int b)
{
	e[idx]=b;
	ne[idx]=h[a];
	h[a]=idx++;
}
void dfs(int u)
{
	for(int i=h[u];i!=-1;i=ne[i])
	{
		int son=e[i];
		dfs(son);
		//根节点必须选上
		//所以从m-1开始，留出根节点的位置  
		for(int j=m-1;j>=0;j--)
			for(int k=1;k<=j;k++)
				f[u][j+1]=max(f[u][j+1],f[u][j+1-k]+f[son][k]); 
	}
	//再把每个物品塞进去
	//因为上面留出位置
	for(int i=m;i;i--)
		f[u][i]+=w[u];
	f[u][0]=0;
}
int main()
{
	cin>>n>>m;
	memset(h,-1,sizeof h);
	for(int i=1;i<=n;i++)
	{
		int fa;
		cin>>fa>>w[i];
		add(fa,i);
	}
	//0是虚拟源点
	//所以相当于多选了一个 
	m++;
	dfs(0);
	cout<<f[0][m]<<endl;
	return 0;
}