1. 题目

题目链接：P2014「[CTSC1997]选课」 。

题目描述

在大学里每个学生，为了达到一定的学分，必须从很多课程里选择一些课程来学习，在课程里有些课程必须在某些课程之前学习，如高等数学总是在其它课程之前学习。现在有 $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 \leq {k_i} \leq N$，$1 \leq {s_i} \leq 20$）。

输出格式

只有一行，选 $M$ 门课程的最大得分。

输入输出样例

输入 #1

7  4
2  2
0  1
0  4
2  1
7  1
7  6
2  2

输出 #1

13

2. 题解

分析

树上 dp + 背包问题的结合，即树上背包。有题意可知，最终这些课程构成一个森林，我们不妨将 $0$ 号结点看作所有树的根，其学分为 $0$，则我们将森林转为一棵树来处理：

• 首先构建状态：设 $f[i][j]$ 表示以 $i$ 号结点为根容许选 $j$ 门课的子树的最大学分。

• 然后构建状态转移方程：遍历结点 $u$ 的每个孩子 $v$，计算转移方程

$$f[i][j] = \max_{1 \leq k \leq j-1}\{f[i][j], f[i][j-k]+f[v][k]\}$$

即对于当前结点 $i$ 有 $j$ 的容量、分 $k$ 的容量给 $v$ 子树得到的最大学分。

注意

• 首先，对于每个孩子 $v$ 而言，$j$ 应当从最大递减逆序枚举，因为需要保证 $f[i][j-k]$ 的最优解不是来源于 $v$ 子树（因为 $f[v][k]$ 已经是来源于 $v$ 子树的）。
• 其次，遍历每个孩子 $v_l$ 时 $j$ 的范围时不一样的。因为对于已经遍历过的子树而言，我们需要考虑其也有可能对最优解产生贡献，因此需要将 $j$ 的范围扩大到包括所有已遍历的子树大小（但不能超过 $m+1$）。设 $res$ 为已经遍历的子树的大小之和，则 $j$ 的范围为

$$j \in [1,min(res,m+1)]$$

• 最后，需要计算结点 $i$ 所有可能容量的最优解，然后向上更新父结点。以此类推。

求解过程可以采用自顶向下的方法，即利用树的递归性质，采用 DFS 遍历整棵树，每次遍历完子树后再更新当前结点；也可以采用自底向上的方法，首先构建一个队列，将孩子数为 $0$ 的结点加入队列中。然后从队列中取出结点开始更新，每次更新完都将父结点的孩子树减 $1$，然后将孩子树为 $0$ 的父结点加入队列中（本质是一个拓扑序列，将父子结点的边看作是孩子到父亲的有向边）。

代码

DFS 计算子树最优解

#include <bits/stdc++.h>
#define ll int
#define MAXN 305
using namespace std;

// 前向星存边
ll cnt;
ll head[MAXN];
struct edge{
    ll to;
    ll next;
}e[MAXN];
void init() {
    cnt = 0;
    memset(head, -1, sizeof(head));
}
void addEdge(ll u, ll v) {
    e[cnt].to = v;
    e[cnt].next = head[u];
    head[u] = cnt++;
}

ll k[MAXN];         // 父结点
ll s[MAXN];         // 权值
ll dp[MAXN][MAXN];  

// dfs
ll dfs(ll u, ll m) {
    ll res = 1;
    dp[u][1] = s[u];
    for(ll i = head[u]; i != -1; i = e[i].next) {
        ll curres = dfs(e[i].to, m-1);
        // 剩余 j 门课
        for(ll j = min(res, m); j; --j) {
            for(ll ii = 1; ii <= curres && j+ii <= m; ++ii) {
                dp[u][j+ii] = max(dp[u][j+ii], dp[u][j] + dp[e[i].to][ii]);
            }
        }
        res += curres;
    }
    return res;
}

int main()
{
    ll n, m;
    init();
    scanf("%d%d", &n, &m);
    for(ll i = 1; i <= n; ++i) {
        ll ki, si;
        scanf("%d%d", &ki, &si);
        k[i] = ki;
        s[i] = si;
        addEdge(ki, i);
    }
    dfs(0, m+1);
    printf("%d\n", dp[0][m+1]);
    return 0;
}

拓扑排序计算子树最优解

#include <bits/stdc++.h>
#define ll int
#define MAXN 305
using namespace std;

// 前向星存边
ll cnt;
ll head[MAXN];
struct edge{
    ll to;
    ll next;
}e[MAXN];
void init() {
    cnt = 0;
    memset(head, -1, sizeof(head));
}
void addEdge(ll u, ll v) {
    e[cnt].to = v;
    e[cnt].next = head[u];
    head[u] = cnt++;
}

ll k[MAXN];         // 父结点
ll s[MAXN];         // 权值
ll in[MAXN];        // 入度
ll sz[MAXN];        // 子树大小
ll dp[MAXN][MAXN];  

void answer(ll n, ll m) {
    queue <ll> q;
    for(int i = 0; i <= n; ++i) {
        if(!in[i]) {
            dp[i][1] = s[i];
            sz[i] = 1;
            --in[k[i]];
            ++sz[k[i]];
            if(!in[k[i]]) {
                ++sz[k[i]];
                q.push(k[i]);
            }
        }
    }
    while(q.size()) {
        ll p = q.front();
        q.pop();
        ll res = 1;
        dp[p][1] = s[p];
        for(ll i = head[p]; i != -1; i = e[i].next) {
            ll u = e[i].to;
            for(ll j = min(res, m+1); j; --j) {
                for(ll d = 1; d <= sz[u] && d+j <= m+1; ++d) {
                    dp[p][d+j] = max(dp[p][d+j], dp[p][j]+dp[u][d]);
                }
            } 
            res += sz[u];
        }
        --in[k[p]];
        sz[k[p]] += sz[p];
        if(!in[k[p]]) {
            ++sz[k[p]];
            q.push(k[p]);
        }
    }
}

int main()
{
    ll n, m;
    init();
    scanf("%d%d", &n, &m);
    for(ll i = 1; i <= n; ++i) {
        ll ki, si;
        scanf("%d%d", &ki, &si);
        k[i] = ki;
        s[i] = si;
        ++in[ki];
        addEdge(ki, i);
    }
    answer(n, m);
    printf("%d\n", dp[0][m+1]);
    return 0;
}