zerosea.tfcis.org:8080/JudgeOnline/showproblem?problem_id=1152

樹型依賴背包

看了學長的培訓講義才會的

#include <stdio.h>  
#include <vector>  
#include <algorithm>  
using namespace std;  

int dp[501][5001];  
int v[501], w[501];  
int n, m;  
vector<int> G[501];  
int dfs(int mom, int W)  
{  
 for (int i = 0; i < G[mom].size(); i++) {  
 int chl = G[mom][i];  
 dp[chl][W] = dp[mom][W];  
 dp[mom][W] = max(dp[mom][W], dfs(chl, W));  
 }  
 if (w[mom] > W) {  
 return 0;  
 }  
 return dp[mom][W - w[mom]] + v[mom];  
}  
int main()  
{  
 int t;  
 scanf("%d", &t);  
 while (t--) {  
 scanf("%d%d", &n, &m);  
 v[0] = w[0] = 0;  
 int dep;  
 for (int i = 1; i <= n; i++) {  
 scanf("%d%d%d", &dep, &w[i], &v[i]);  
 G[dep].push_back(i);  
 }  
 for (int i = 1; i <= m; i++) {  
 dp[0][i] = 0;  
 dp[0][i] = max(dp[0][i], dfs(0, i));  
 }  
 printf("%d\n", dp[0][m]);  
 for (int i = 0; i <= n; i++) {  
 G[i].clear();  
 }  
 }  
 return 0;  
}