1. 题目

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

题目描述

在大学里每个学生,为了达到一定的学分,必须从很多课程里选择一些课程来学习,在课程里有些课程必须在某些课程之前学习,如高等数学总是在其它课程之前学习。现在有 NN 门功课,每门课有个学分,每门课有一门或没有直接先修课(若课程 aa 是课程 bb 的先修课即只有学完了课程 aa,才能学习课程 bb)。一个学生要从这些课程里选择 MM 门课程学习,问他能获得的最大学分是多少?

输入格式

第一行有两个整数 NNMM 用空格隔开。(1N3001 \leq N \leq 3001M3001 \leq M \leq 300

接下来的 NN 行,第 I+1I+1 行包含两个整数 kik_isis_ikik_i 表示第 II 门课的直接先修课,sis_i 表示第 II 门课的学分。若 ki=0k_i=0 表示没有直接先修课(1kiN1 \leq {k_i} \leq N1si201 \leq {s_i} \leq 20)。

输出格式

只有一行,选 MM 门课程的最大得分。

输入输出样例

输入 #1

1
2
3
4
5
6
7
8
7  4
2 2
0 1
0 4
2 1
7 1
7 6
2 2

输出 #1

1
13

2. 题解

分析

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

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

  • 然后构建状态转移方程:遍历结点 uu 的每个孩子 vv,计算转移方程

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

即对于当前结点 iijj 的容量、分 kk 的容量给 vv 子树得到的最大学分。

注意

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

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

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

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

代码

DFS 计算子树最优解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#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;
}

拓扑排序计算子树最优解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#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;
}