洛谷P2014 选课 - 树上背包

注意在dp中x！=0那一段 其实是对状态的修正

#include <algorithm>
#include <iostream>
#include <cstdio>
using namespace std;
const int MAXN = 300 + 10;
int n,m,tot,head[MAXN],k[MAXN],son[MAXN],f[MAXN][MAXN];
struct Edge{
int u,v,to;
Edge(){}
Edge(int u, int v, int to) : u(u), v(v), to(to) {};
}e[MAXN];
inline void add(int u, int v) {
e[++tot] = Edge(u,v,head[u]);
head[u] = tot;
}
void dfs(int x) {
if(!head[x]) son[x] = 1;
for(int i=head[x]; i; i=e[i].to) {
dfs(e[i].v);
son[x] += son[e[i].v];
}
}
void dp(int x) {
for(int i=head[x]; i; i=e[i].to) {
int v = e[i].v;
dp(v);
for(int t=m; t>=0; t--)
for(int j=t; j>=0; j--)
f[x][t] = max(f[x][t], f[v][j] + f[x][t-j]);
}
if(x != 0)
for(int t=m; t>0; t--)
f[x][t] = f[x][t-1] + k[x];
}
int main() {
scanf("%d %d", &n, &m);
for(int i=1; i<=n; i++) {
int u;
scanf("%d %d", &u, &k[i]);
if(u != 0)
add(u, i);
else
add(0, i);// ³¬¼¶Ô´µã0 
}
dfs(0);
dp(0);
printf("%dn", f[0][m]);
return 0;
}

最后

以上就是轻松宝马为你收集整理的洛谷P2014 选课 - 树上背包的全部内容，希望文章能够帮你解决洛谷P2014 选课 - 树上背包所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。