【Vijos1180】选课

problem

solution

codes

//vijos 1180
#include<iostream>
#include<vector>
using namespace std;
struct Edge { int w;  vector<int>to; }G[1010];
int f[1010][1010];
//dfs(x,y)表示在x为根的子树中选y节课的最大学分。
void dfs(int x, int y){
    for(int i = 0; i < G[x].to.size(); i++){
        int tmp = G[x].to[i];
        for(int j = 0; j <= y; j++)
            f[tmp][j] = f[x][j]+G[tmp].w;
        dfs(tmp,y-1);
        for(int j = 0; j <= y; j++)
            f[x][j] = max(f[x][j], f[tmp][j-1]);
    }
}
int main(){
    int n, m;
    cin>>n>>m;
    for(int i = 1; i <= n; i++){
        int a, b; cin>>a>>b;
        G[a].to.push_back(i);
        G[i].w = b;
    }
    dfs(0, m);
    cout<<f[0][m];
    return 0;
}
  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
 

文章来源: gwj1314.blog.csdn.net，作者：小哈里，版权归原作者所有，如需转载，请联系作者。

原文链接：gwj1314.blog.csdn.net/article/details/80530635