题意：有N门课，不同的课有不同的学分，但是有些课必须要选修先修课才能选，求出选 M 门课程的最大得分。

同样是一道非常简单的题，去掉不同课之间的先修关系，这道题的就是一道非常普通的0 1 背包问题，M为容量，得分为价值。加上选修课之间的关系之后，很容易就能构造出一个树状的模型。
先修课为父节点，选了先修课才能选之后的课，因此之后的课就是先修课的子节点。
这道题的关系比较复杂，父节点有可能有多个子节点，题目中也有可能有多个祖先节点。那么便不能用普通的方法暴力存图。这里我首推链式前向星，当然用邻接表等方法存图也可以 = = 。
（这里我就不详述了）

定义一个struct，和一个head数组

struct node {
    int next,to,s;
}t[310];
int head[310];

输入之前将所有点初始化为-1

    memset(head, -1, sizeof head);
    memset(t, -1, sizeof t);
    for (int i = 1; i <= n; i++, cnt++) {
        cin >> k >> s;
        t[cnt].next = head[k];
        t[cnt].s = s;
        head[k] = cnt;
        t[cnt].to = i;
    }
    m++;

因为题目中没说只有一个祖宗节点，也就是说题目内可能有很多的树，所以我们需要自己定义一个虚拟的祖宗节点，且权值为0，从这个虚拟的祖宗节点开始遍历，就能方便地处理这种很多棵树的问题，这题是计算点的权值。

状态转移方程

dp[ i ][ j ] = max(dp[ i ][ j ], dp[ i ][ j - k ] + dp[ i-1 ][k])

dp[ i ][ j ]代表选 j 门第 i 门课的子课能拿到的最大学分

ac代码

#include<iostream>
#include<cstring>
using namespace std;
struct node {
    int next,to,s;
}t[310];
int head[310],judge[310];
int dp[310][310];
int n, m, k, s, cnt = 1;
void az(int x) {
    for (int i = head[x]; i != -1; i = t[i].next) {
        az(t[i].to);
        for (int j = m - 1; j >= 0; j--) {
            for (int k = 1; k <= j; k++) {
                dp[x][j] = max(dp[x][j], dp[x][j - k] + dp[t[i].to][k]);    
            }
        }
    }
    for (int i = m; i ; i--) {
        dp[x][i] = dp[x][i - 1] + t[x].s;
    }
}
int main()
{
    cin >> n >> m;
    memset(head, -1, sizeof head);
    memset(t, -1, sizeof t);
    for (int i = 1; i <= n; i++, cnt++) {
        cin >> k >> s;
        t[cnt].next = head[k];
        t[cnt].s = s;
        head[k] = cnt;
        t[cnt].to = i;
    }
    m++;//因为多一个虚拟节点，所以计算的是m+1门课
    t[0].s = 0;
    az(0);
    cout << dp[0][m] << endl;
}