题目描述
在大学里每个学生，为了达到一定的学分，必须从很多课程里选择一些课程来学习，在课程里有些课程必须在某些课程之前学习，如高等数学总是在其它课程之前学习。现在有N门功课，每门课有个学分，每门课有一门或没有直接先修课（若课程a是课程b的先修课即只有学完了课程a，才能学习课程b）。一个学生要从这些课程里选择M门课程学习，问他能获得的最大学分是多少？
输入输出格式
输入格式：
第一行有两个整数N,M用空格隔开。(1<=N<=300,1<=M<=300)
接下来的N行,第I+1行包含两个整数ki和si, ki表示第I门课的直接先修课，si表示第I门课的学分。若ki=0表示没有直接先修课（1<=ki<=N, 1<=si<=20）。
输出格式：
只有一行，选M门课程的最大得分。
输入输出样例
输入样例#1： 复制
7 4
2 2
0 1
0 4
2 1
7 1
7 6
2 2
输出样例#1： 复制
13 f(i,j)代表以i为节点的子树（不选i）选j个附属元素产生的最大学分
状态转移方程为：f[u][i]=max(f[u][i],f[u][i-j-1]+f[v][j]+e[p].w);
（i-j-1的-1是因为从定义来看v这个节点本身没有被选啊）
再设个0 节点为总根，f(0,m)就是结果了
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define inf 2147483647
const ll INF = 0x3f3f3f3f3f3f3f3fll;
#define ri register int
template <class T> inline T min(T a, T b, T c)
{
return min(min(a, b), c);
}
template <class T> inline T max(T a, T b, T c)
{
return max(max(a, b), c);
}
template <class T> inline T min(T a, T b, T c, T d)
{
return min(min(a, b), min(c, d));
}
template <class T> inline T max(T a, T b, T c, T d)
{
return max(max(a, b), max(c, d));
}
#define pi acos(-1)
#define me(x, y) memset(x, y, sizeof(x));
#define For(i, a, b) for (int i = a; i <= b; i++)
#define FFor(i, a, b) for (int i = a; i >= b; i--)
#define mp make_pair
#define pb push_back
const int maxn = ;
#define mod 100003
const int N=; // name*******************************
int f[][];
int s[];
int n,m;
struct edge
{
int to,next,w;
} e[];
int tot=;
int Head[];
int ans=;
// function******************************
void add(int u,int v,int w)
{
e[++tot].to=v;
e[tot].next=Head[u];
e[tot].w=w;
Head[u]=tot;
}
int dfs(int u)
{
int cnt=;
for(int p=Head[u]; p!=-; p=e[p].next)
{
int v=e[p].to;
int t=dfs(v);
cnt+=t+;
FFor(i,min(m,cnt),)
For(j,,min(t,i-))
{
f[u][i]=max(f[u][i],f[u][i-j-]+f[v][j]+e[p].w);
}
}
return cnt;
} //***************************************
int main()
{
cin>>n>>m;
int a,b;
me(Head,-);
For(i,,n)
{
cin>>a>>b;
if(a==)
add(,i,b);
else
add(a,i,b);
}
dfs();
cout<<f[][m]; return ;
}