题目描述
在大学里每个学生，为了达到一定的学分，必须从很多课程里选择一些课程来学习，在课程里有些课程必须在某些课程之前学习，如高等数学总是在其它课程之前学习。现在有(N)门功课，每门课有个学分，每门课有一门或没有直接先修课（若课程(a)是课程(b)的先修课即只有学完了课程(a)，才能学习课程(b)）。一个学生要从这些课程里选择(M)门课程学习，问他能获得的最大学分是多少？
输入输出格式
输入格式：
第一行有两个整数N,M用空格隔开。
((1 leq N leq 300,1 leq M leq 300))
接下来的(N)行,第(I+1)行包含两个整数(k_i)和(s_i, k_i)表示第I门课的直接先修课，(s_i)表示第(I)门课的学分。若(k_i=0)表示没有直接先修课（(1<=k_i<=N, 1<=s_i<=20)）。
输出格式：
只有一行，选(M)门课程的最大得分。
输入输出样例
输入样例#1：
7 4
2 2
0 1
0 4
2 1
7 1
7 6
2 2
输出样例#1：
13
思路：数据范围也不是特别大，可以考虑树型(dp)，首先，建图就是按照题目所给的信息建有向边，之后我们用(f[i][j])表示以(i)为顶点，选了(j)门课程的最大得分，然后(dfs)时枚举每条与一个点相连的边，用这个结点去更新它的子节点为顶点时的初始值，然后遍历完它所有的子节点之后，再回过头来更新这个结点为顶点时的最大值。
代码：
#include<cstdio>
#include<algorithm>
#define maxn 307
using namespace std;
int n,m,head[maxn],f[maxn][maxn],w[maxn],num;
struct node {
int v,nxt;
}e[maxn];
inline void ct(int u, int v) {
e[++num].v=v;
e[num].nxt=head[u];
head[u]=num;
}
void dfs(int u, int k) {
for(int i=head[u];i;i=e[i].nxt) {
int v=e[i].v;
for(int j=k+1;j<=m+1;++j) f[v][j]=f[u][j-1]+w[v];
dfs(v,k+1);
for(int j=k+1;j<=m+1;++j) f[u][j]=max(f[u][j],f[v][j]);
}
}
int main() {
scanf("%d%d",&n,&m);
for(int i=1,u;i<=n;++i) {
scanf("%d%d",&u,&w[i]);
ct(u,i);
}
dfs(0,1);
printf("%d
",f[0][m+1]);
return 0;
}