P2515: Software Installation [HAOI2010]

Problem Description: You have computer with M amount of storage. There are N softwares you are going to install on the computer. The ith computer takes amount of storage and has a value of . There are also dependencies between softwares. Specifically, the ith software can be installed only if   is installed. Every software can be only installed once, please output the maximum value you can reach by installing softwares while following the dependency rule and not exceeding the storage limit. 

Input Format:
The first line contains two numbers N ≤ 100,M ≤ 500  
The second line contains N numbers represent
The third line contains N numbers represent
The fourth line contains N numbers represent . Note that if it is zero, then it means this software does not depend on any other software.

Output Format:
One Line represent the maximum value.

Sample Input:
3 10
5 5 6
2 3 4
0 1 1

Sample Output:
5

Solution: At first, I thought this is just a tree DP problem. This initial direction is correct, but the thing is that it is also possible to have a cycle on the graph. Therefore, we need to use Tarjan Algorithm to calculate all SCC(strongly connected components), and then we rebuild the graph based on the new grouping. Now, the entire graph is a tree, and we can use tree DP to solve the problem. We use f[u][i] to denote the maximum value at tree node u with i amount of storage. We know that the following equation holds.

$$f[u][i + W_{u}]_{i≤M – W_{u}} = \max_{v∈u, j≤i}(f[u][i + W_{u} – j] + f[v][j])$$

Initially, we set all f[u][i] = where i ≥ .

#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <stdio.h>
#include <fstream>
#include <cmath>
#include <stdlib.h>
#include <iomanip>
#include <algorithm>
#include <limits.h>
#include <stack>
using namespace std;
#define FAST_IO ios::sync_with_stdio(false);
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
typedef pair<double,double> pdd;
typedef long long ll;
const int maxn = 1005;
int N,M;
struct software{
    int val,space,dep;
    software(int a = 0,int b = 0,int c = 0):val(a),space(b),dep(c){};
} a[maxn],b[maxn];
int deg[maxn],f[maxn][maxn],dfn[maxn],low[maxn],group[maxn],gp_cnt;
stack<int> S;
vector<int> G1[maxn],G2[maxn];
queue<int> q;
void addedge1(int u,int v){
    G1[u].push_back(v);
}
void addedge2(int u,int v){
    G2[u].push_back(v);
}
int dfs_clock;
void tarjan(int u){
    dfn[u] = low[u] = ++dfs_clock;
    S.push(u);
    for(int i = 0; i < G1[u].size(); i++){
        int v = G1[u][i];
        if(!dfn[v]){
            tarjan(v);
            low[u] = min(low[u],low[v]);
        }
        else if(!group[v]){
            low[u] = min(low[u],dfn[v]);
        }
    }
    if(low[u] == dfn[u]){
        gp_cnt++;
        for(;;){
            int x = S.top(); S.pop();
            group[x] = gp_cnt;
            if(x == u) break;
        }
    }
}
void dfs(int u){
    for(int i = b[u].space; i <= M; i++) f[u][i] = b[u].val;
    for(int i = 0; i < G2[u].size(); i++){
        int v = G2[u][i];
        dfs(v);
        for(int j = M - b[u].space; j >= 0; j--){
            for(int k = 0; k <= j; k++){
                f[u][j + b[u].space] = max(f[u][j + b[u].space],f[u][j + b[u].space - k] + f[v][k]);
            }
        }
    }
}
int main(){
    FAST_IO
    cin>>N>>M;
    for(int i = 1; i <= N; i++) cin>>a[i].space;
    for(int i = 1; i <= N; i++) cin>>a[i].val;
    for(int i = 1; i <= N; i++) {cin>>a[i].dep; if(a[i].dep) addedge1(a[i].dep,i);};
    for(int i = 1; i <= N; i++){
        if(!group[i]) tarjan(i);
    }
    for(int i = 1; i <= N; i++){
        b[group[i]].space += a[i].space;
        b[group[i]].val += a[i].val;
    }
    for(int i = 1; i <= N; i++){
        if(a[i].dep && group[a[i].dep] != group[i]){
            deg[group[i]]++;
            addedge2(group[a[i].dep],group[i]);
        }
    }
    for(int i = 1; i <= N; i++){
        if(!deg[group[i]]){
            addedge2(gp_cnt + 1,group[i]);
        }
    }
    dfs(gp_cnt + 1);
    int ans = 0;
    for(int i = 0; i <= M; i++) ans = max(ans,f[gp_cnt + 1][i]);
    cout<<ans<<endl;
    return 0;
}