Thursday, March 8, 2012

[code] UPRC-1152 佈置問題

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;
}
  

2 comments: