【题目来源】
https://www.luogu.com.cn/problem/P2014
【题目描述】
在大学里每个学生，为了达到一定的学分，必须从很多课程里选择一些课程来学习，在课程里有些课程必须在某些课程之前学习，如高等数学总是在其它课程之前学习。现在有 N 门功课，每门课有若干学分，分别记作 s1，s2，…，sN，每门课有一门或没有直接先修课（若课程 a 是课程 b 的先修课即只有学完了课程 a，才能学习课程 b）。一个学生要从这些课程里选择 M 门课程学习，问他能获得的最大学分是多少？
题目保证课程安排无冲突。（即不会有 a 是 b 的先修课，b 也是 a 的先修课这类情况存在。）
【输入格式】
第一行有两个整数 N，M 用空格隔开(1≤N≤300，1≤M≤300)。
接下来的 N 行，第 i+1 行包含两个整数 ki 和si，ki 表示第 i 门课的直接先修课，si 表示第 i 门课的学分。若 ki=0 表示没有直接先修课（0≤ki≤N，1≤si≤20)。
数据保证至少存在一个 ki=0，即至少一门课无先修课。
【输出格式】
只有一行，选 M 门课程的最大学分。
【输入样例】
7 4
2 2
0 1
0 4
2 1
7 1
7 6
2 2
【输出样例】
13
【数据范围】
1≤N≤300，1≤M≤300
0≤ki≤N，1≤si≤20
【算法分析】
● 有依赖的背包（树形背包）核心是物品间存在选子必选父的单向依赖关系，依赖结构通常为森林或多叉树，主流解法为树形 DP 结合分组背包自底向上合并；若题目中是双向强依赖、互相绑定的物品组（选其一必全选），则可先用并查集将连通块缩为超级物品，再套用普通 01 背包求解，两种思路对应不同依赖模型，共同构成完整解法体系。
● 链式前向星：https://blog.csdn.net/hnjzsyjyj/article/details/139369904
大佬 yxc 指出“链式前向星”就是“多单链表”，每条单链表基于“头插法”并用 e[]、ne[]、h[] 、val[] 等数组进行模拟创建。其中：
e[idx]：存储序号为 idx 的边的终点值
ne[idx]：存储序号为 idx 的边指向的边的序号（模拟链表指针）
h[a]：存储头结点 a 指向的边的序号
val[idx]：存储序号为 idx 的边的权值（可选）
● 由于选课必须遵循先选父节点、再选子节点的依赖规则，因此每棵子树都可以视为一个独立的分组。我们直接以选课门数作为背包容量，通过倒序循环实现类 0/1 背包的转移方式，从而避免同一子树被重复选择，并最终利用分组背包的思路合并得到所有子树的最优解。
● 为什么循环要写 j=m+1？因为我们加了虚拟根节点 0，它本身要占 1 个名额，所以实际要选的数量=m+1。
● f[u][j]：在以课程 u 为根的子树内（包含课程 u 本身），恰好选取 j 门课程时能获得的最大学分。显然，在此约束下，f[u][1] 表示 u 这门课的学分。
● 核心代码解析：
（1）for(int j = m+1; j >= 1; j--) → 现在要一共选 j 门课，j 从大往小试。
（2）for(int k = 0; k < j; k++) → 拿出 k 门课的名额，给子课 t。剩下的 j - k 门课，留给 u 自己。
（3）f[u][j]=max(f[u][j],f[t][k]+f[u][j-k]); → 在以 u 为根的子树中选取 j 门课程时，这 j 个名额只能由两部分构成：一部分是尚未纳入当前子树 t 时、u 原本已计算好的选课方案，另一部分则是当前子树 t 的选课方案。因此我们可以将 j 个名额拆分为分配给子树 t 的 k 门课程，以及留给 u 原有方案的 j−k 门课程。由于子树 t 和 u 原有部分的最优解均已提前算出，二者相加即为该分配方式下的最优总分，再通过枚举所有合理的 k 值，选取其中分数最大的结果，便可得到 f [u][j] 的最终最优解。
【算法代码】
#include <bits/stdc++.h>
using namespace std;const int N=305;
int e[N],ne[N],h[N],idx;
int f[N][N];
int n,m;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 t=e[i]; //one of the sub-courses of udfs(t);//j = How many courses have you selected?for(int j=m+1; j>=1; j--) {//k = Assign k courses to the sub-courses tfor(int k=0; k<j; k++) {f[u][j]=max(f[u][j],f[t][k]+f[u][j-k]);}}}
}int main() {memset(h,-1,sizeof h);cin>>n>>m; //Choose m courses out of n coursesfor(int i=1; i<=n; i++) {int fa; //Pre-requisite Course Numbercin>>fa>>f[i][1];add(fa,i); //Add edge: prerequisite fa -> course i}dfs(0);cout<<f[0][m+1];return 0;
}/*
in:
7 4
2 2
0 1
0 4
2 1
7 1
7 6
2 2out:
13
*/
【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/159616887
https://blog.csdn.net/hnjzsyjyj/article/details/159618980