BZOJ 2427 HAOI 2010 소프트웨어 설치 Tarjan + 트리 DP

제목의 대의: 각 점마다 하나의 의존 노드가 있는 그림을 보여 준다. 한 노드를 선택할 때 반드시 이 노드의 의존 노드를 선택해야만 이 노드의 권한을 얻을 수 있다.각 점마다 하나의 공간이 있는데 전체 공간의 제한을 주고 최대 얼마의 권한을 얻을 수 있는지 물어본다.
사고방식: 한 고리에 나타난 점은 모두 선택하든지 아니면 모두 선택하지 않든지 간에 먼저 점을 줄이고 그 다음에 나무가 되어 나무에 배낭을 만들면 된다.
CODE:

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define MAX 2010
using namespace std;
 
int head[MAX],total;
int next[MAX],aim[MAX];
 
inline void Add(int x,int y)
{
    next[++total] = head[x];
    aim[total] = y;
    head[x] = total;
}
 
int cost[MAX],val[MAX];
int father[MAX];
 
int cnt,all;
 
int dfn[MAX],low[MAX],_clock;
int stack[MAX],top;
bool in_stack[MAX];
int changed[MAX],scc;
 
void Tarjan(int x)
{
    dfn[x] = low[x] = ++_clock;
    stack[++top] = x;
    in_stack[x] = true;
    for(int i = head[x]; i; i = next[i]) {
        if(!dfn[aim[i]])
            Tarjan(aim[i]),low[x] = min(low[x],low[aim[i]]);
        else if(in_stack[aim[i]])
            low[x] = min(low[x],dfn[aim[i]]);
    }
    if(dfn[x] == low[x]) {
        scc++;
        int temp;
        do {
            temp = stack[top--];
            in_stack[temp] = false;
            changed[temp] = scc;
        }while(temp != x);
    }
}
 
struct Graph{
    int head[MAX],total;
    int next[MAX],aim[MAX];
     
    int _in[MAX],f[MAX][MAX];
    int cost[MAX],val[MAX];
     
    void Add(int x,int y) {
        next[++total] = head[x];
        aim[total] = y;
        head[x] = total;
        ++_in[y];
    }
    void DP(int x) {
        for(int i = head[x]; i; i = next[i]) {
            DP(aim[i]);
            for(int j = all - cost[x]; j >= 0; --j)
                for(int k = 0; k <= j; ++k)
                    f[x][j] = max(f[x][j],f[x][k] + f[aim[i]][j - k]);
        }
        for(int i = all; i; --i) {
            if(i >= cost[x]) f[x][i] = f[x][i - cost[x]] + val[x];
            else    f[x][i] = 0;
        }
    }
    int GetAns() {
        memset(f,0,sizeof(f));
        int S = 0;
        for(int i = 1; i <= scc; ++i)
            if(!_in[i])
                Add(S,i);
        DP(S);
        return f[S][all];
    }
}graph;
 
int main()
{
    cin >> cnt >> all;
    for(int i = 1; i <= cnt; ++i)
        scanf("%d",&cost[i]);
    for(int i = 1; i <= cnt; ++i)
        scanf("%d",&val[i]);
    for(int x,i = 1;i <= cnt; ++i) {
        scanf("%d",&x);
        if(x)   Add(x,i);
    }
    for(int i = 1; i <= cnt; ++i)
        if(!dfn[i]) Tarjan(i);
    for(int x = 1; x <= cnt; ++x)
        for(int i = head[x]; i; i = next[i])
            if(changed[x] != changed[aim[i]])
                graph.Add(changed[x],changed[aim[i]]);
    for(int i = 1; i <= cnt; ++i) {
        graph.cost[changed[i]] += cost[i];
        graph.val[changed[i]] += val[i];
    }
    cout << graph.GetAns() << endl;
    return 0;
}