大概思路 :
建一个超级源点,对所有没有依赖的点建边,边权为出点的点权。
定义f[i][j]为以i为根的恰好选中j个点的最大权重(选中的点一定得包含根节点),
那么可以知道我们要求的答案就是f[root][m + 1],root为超级源点,m为题目需要的课程数,
由于选中的点(课程)一定包含根节点,所以答案的 m 要 + 1。
转移方程就是f[u][j] = max(f[u][j],f[u][j - k] + f[v][k] ),其中u为根节点,v为u的某个连接的子节点,
j 为枚举的课程数 ,k为分配给v的可以选择的课程数,j - k就是自己选择的课程数
由于我们是必须选择根节点的,所以我们可以在状态转移前,将所有根为u的状态的值初始化为u的点权,
并且使 j > k ,这样转移的时候就可以确保我们的每一次转移都会恰好记录一次 u 的点权。
题目描述
在大学里每个学生,为了达到一定的学分,必须从很多课程里选择一些课程来学习,在课程里有些课程必须在某些课程之前学习,如高等数学总是在其它课程之前学习。现在有 $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
样例输入 #1
7 4
2 2
0 1
0 4
2 1
7 1
7 6
2 2
样例输出 #1
13
C++ 代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define rep(a,b,c) for (int a = b ; a < c ; ++a)
using namespace std;
typedef long long ll ;
typedef pair<int,int> pii ;
const int maxn = 310 ;
char c,num[15];bool F;int len;
template <typename T>
inline void R(T &x){
x = 0,F = 0,c = getchar();
while (c < '0' || c > '9' ){if (c == '-') F = 1;c = getchar();}
while (c >= '0'&& c <= '9' ){x = (x << 3) + (x << 1) + (c & 15) ; c = getchar() ;}
if (F) x = -x ;
}
template <typename T>
inline void W(T x) {
if (!x) putchar('0');
len = 0;
if (x < 0) putchar('-'), x = -x;
while(x) num[++len] = (x % 10) + 48, x /= 10;
while(len) putchar(num[len--]);
}
int h[maxn],nxt[maxn],to[maxn],w[maxn],vertex[maxn],tot,f[maxn][maxn],n,m;
inline void add(int u,int v,int val){
nxt[++tot] = h[u],h[u] = tot,to[tot] = v,w[tot] = val;
}
inline int dfs(int u){
int cnt = f[u][1];
vertex[u] = 1 ;
for (int i = h[u], v = to[i] ; i ; i = nxt[i],v = to[i])
f[v][1] = w[i],cnt += dfs(v),vertex[u] += vertex[v];
f[u][vertex[u]] = cnt ;
rep(i,2,vertex[u])
f[u][i] = f[u][1];
for (int i = h[u], v = to[i] ; i ; i = nxt[i],v = to[i]) // f[i][j] 表示以i为根,选中j个点的最大学分
for (int j = min(m + 1,vertex[u] - 1) ; j >= 2; -- j )
for (int k = 1 ; k <= vertex[v] && j > k ; ++k)
f[u][j] = max(f[u][j],f[u][j - k] + f[v][k] );
return cnt ;
}
int main(){
R(n),R(m);
int root = 301,a,b;
rep(i,1,n + 1){
R(a),R(b);
add(a ? a : root,i,b);
}
dfs(root);
W(f[root][m + 1]);
return 0;
}
优秀