在大学里每个学生，为了达到一定的学分，必须从很多课程里选择一些课程来学习，在课程里有些课程必须在某些课程之前学习，如高等数学总是在其它课程之前学习。现在有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门课程的最大得分。
7 4 2 2 0 1 0 4 2 1 7 1 7 6 2 2
13
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
int max(int x,int y){
return x>y?x:y;
}
struct node{
int data;
node *next;
node(){
next=NULL;
}
};
node head[301],*tail[301];
int f[301][301],s[301],n,m,p[301];
void dfs(int x){
node *root;
root=&head[x];
node *r=root->next;
while(root->next!=0){
root=root->next;
dfs(root->data);
s[x]+=s[root->data];
}
while(r!=0){
for(int k=s[x];k>=1;k--){
for(int j=1;j<=k;j++){
f[x][k]=max(f[x][k],f[x][k-j]+f[r->data][j]);
}
}
r=r->next;
}
for(int i=s[x];i>=0;i--)
f[x][i+1]=f[x][i]+p[x];
return ;
}
int main(){
memset(s,0,sizeof(s));
memset(f,0,sizeof(f));
int a,b;
scanf("%d%d",&n,&m);
for(int i=0;i<=n;i++){
tail[i]=&head[i];
}
for(int i=1;i<=n;i++){
scanf("%d%d",&a,&b);
s[a]++;
node *t=new node();
t->data=i;
p[i]=b;
tail[a]->next=t;
tail[a]=t;
}
dfs(0);
printf("%d\n",f[0][m+1]);
return 0;
}
原文：https://www.cnblogs.com/xiongchongwen/p/11243449.html