题目描述：
lw很喜欢玩一种战略游戏，在一个地图上，有n座城堡，每座城堡都有一定的宝物，在每次游戏中lw允许攻克m个城堡并获得里面的宝物。但由于地理位置原因，有些城堡不能直接攻克，要攻克这些城堡必须先攻克其他某一个特定的城堡。你能帮lw算出要获得尽量多的宝物应该攻克哪M个城堡吗？
输入格式：
第一行两个数，分别为n和m。接下来n行，每行两个数，第一个数a为攻克这个城堡前必须攻克的城堡，若a为0则该城堡可以直接攻克，第二个数b表示财宝数。
输出格式：
第一行一个数，即最大财宝数。
样例输入：game.in
3 2
0 1
0 2
0 3
样例输出：game.out
5
数据范围：
对于30%的数据，n,m<=100。
对于100%的数据，n,m<=200。
题解：
首先，限制条件是选择m个物品，而每个物品最多选一次，跟0-1背包的区别在于有依赖关系，那么这层依赖关系我们可以借助于一个树来解决。借助dfs，从根节点开始dfs，然后直到叶子节点，回朔的时候进行0-1背包dp。
定义状态dp[i][j]表示在节点i，从以i为根节点的子树下选择j个城市的最大价值
初始化：dp[i][j]=val[i]（i节点的价值）（1 < = j < = m）
转移方程 dp[father][j] = max （dp[father][j] dp[father][k]+dp[child][j-k]）；由前面的dfs可见，我们是用子节点更新父节点，用j枚举父节点选择的城市数，k枚举留给其他子节点选择城市数，那么就可以转移了
注意：此题出给很多初始节点，也就是有很多森林，我们要设置一个超级root连接子树的根节点即可。
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstdlib> #include<cstring> using namespace std; int f[1001][1001],n,m,a[1001]; int gi() { int ans=0,f=1; char i=getchar(); while(i<'0'||i>'9'){if(i=='-')f=-1;i=getchar();} while(i>='0'&&i<='9'){ans=ans*10+i-'0';i=getchar();} return ans*f; } struct node { int to,next; }edge[10001]; int head[1001],size; void putin(int from,int to) { size++; edge[size].to=to; edge[size].next=head[from]; head[from]=size; } void dfs(int r) { for(int i=head[r];i!=-1;i=edge[i].next) { dfs(edge[i].to); for(int j=m;j>=1;j--) for(int k=0;k<=j;k++) f[r][j]=max(f[r][j],f[r][k]+f[edge[i].to][j-k]); } for(int i=m+1;i>=1;i--)f[r][i]=f[r][i-1]+a[r]; } int main() { freopen("game.in","r",stdin); freopen("game.out","w",stdout); int i,j; memset(head,-1,sizeof(head)); n=gi();m=gi(); for(i=1;i<=n;i++) { int c=gi(),b=gi(); a[i]=b; putin(c,i); } dfs(0); printf("%d",f[0][m+1]); return 0; }
