题目描述

在大学里每个学生，为了达到一定的学分，必须从很多课程里选择一些课程来学习，在课程里有些课程必须在某些课程之前学习，如高等数学总是在其它课程之前学习。现在有\(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\n",f[0][m+1]);
  return 0;
}