题目描述
在大学里每个学生，为了达到一定的学分，必须从很多课程里选择一些课程来学习，在课程里有些课程必须在某些课程之前学习，如高等数学总是在其它课程之前学习。现在有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 42 20 10 42 17 17 62 2
输出 #1复制
13
#include#include #include #include #include #include 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;}