题目P2014 [CTSC1997] 选课题目描述在大学里每个学生为了达到一定的学分必须从很多课程里选择一些课程来学习在课程里有些课程必须在某些课程之前学习如高等数学总是在其它课程之前学习。现在有N NN门功课每门课有若干学分分别记作s 1 , s 2 , ⋯ , s N s_1,s_2,\cdots,s_Ns1​,s2​,⋯,sN​每门课有一门或没有直接先修课若课程a aa是课程b bb的先修课即只有学完了课程a aa才能学习课程b bb。一个学生要从这些课程里选择M MM门课程学习问他能获得的最大学分是多少题目保证课程安排无冲突。即不会有a aa是b bb的先修课b bb也是a aa的先修课这类情况存在。输入格式第一行有两个整数N NNM MM用空格隔开( 1 ≤ N ≤ 300 (1 \leq N \leq 300(1≤N≤300,1 ≤ M ≤ 300 ) 1 \leq M \leq 300)1≤M≤300)。接下来的N NN行第i 1 i1i1行包含两个整数k i k_iki​和s i s_isi​k i k_iki​表示第i ii门课的直接先修课s i s_isi​表示第i ii门课的学分。若k i 0 k_i0ki​0表示没有直接先修课( 0 ≤ k i ≤ N (0 \leq {k_i} \leq N(0≤ki​≤N,1 ≤ s i ≤ 20 ) 1 \leq {s_i} \leq 20)1≤si​≤20)。数据保证至少存在一个k i 0 k_i0ki​0即至少一门课无先修课。输出格式只有一行选M MM门课程的最大学分。输入输出样例 #1输入 #17 4 2 2 0 1 0 4 2 1 7 1 7 6 2 2输出 #113思路代码#includebits/stdc.husingnamespacestd;constintN30010;intn,m,f[N][N],w[N];vectorintg[N];voiddfs(intu){f[u][0]0;//不选for(inti0;ig[u].size();i){//选intvg[u][i];dfs(v);for(intjm;j0;j--)//逆序枚举以u为根的子树选的课程数for(intk0;kj;k)//枚举u的子树选的课程数f[u][j]max(f[u][j],f[u][j-k]f[v][k]);}if(u){//加上选择u的学分for(intjm;j0;j--)f[u][j]f[u][j-1]w[u];}}intmain(){cinnm;for(inti1;in;i){intx,y;cinxw[i];g[x].push_back(i);//森林转化为树}dfs(0);coutf[0][m];return0;}结果