python/TangDou/AcWing/DCC/NC19981.cpp

#include <bits/stdc++.h>
using namespace std;

const int N = 110;
const int M = 510;
// 链式前向星
int e[M], h1[N], h2[N], idx, w[M], ne[M];
void add(int h[], int a, int b, int c = 0) {
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}

int n, m;
int W1[N], V1[N];
int W2[N], V2[N], in[N];

int f[N][M]; // 以i为根(不装)的子树装j时的最大价值

// tarjan算法求强连通分量
int stk[N], top;    // tarjan算法需要用到的堆栈
bool in_stk[N];     // 是否在栈内
int dfn[N];         // dfs遍历到u的时间
int low[N];         // 从u开始走所能遍历到的最小时间戳
int ts;             // 时间戳,dfs序的标识,记录谁先谁后
int id[N], scc_cnt; // 强连通分量块的最新索引号
int sz[N];          // sz[i]表示编号为i的强连通分量中原来点的个数
void tarjan(int u) {
    dfn[u] = low[u] = ++ts;
    stk[++top] = u;
    in_stk[u] = 1;
    for (int i = h1[u]; ~i; i = ne[i]) {
        int v = e[i];
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if (in_stk[v])
            low[u] = min(low[u], dfn[v]);
    }

    if (dfn[u] == low[u]) {
        ++scc_cnt; // 强连通分量的序号
        int x;     // 临时变量x,用于枚举栈中当前强连通分量中每个节点
        do {
            x = stk[top--];  // 弹出节点
            in_stk[x] = 0;   // 标识不在栈中了
            id[x] = scc_cnt; // 记录每个节点在哪个强连通分量中
            sz[scc_cnt]++;   // 这个强连通分量中节点的个数+1

            //===========下面两句是本题特殊的地方================
            W2[scc_cnt] += W1[x]; // 记录每个SCC的累加体积和累加价值
            V2[scc_cnt] += V1[x];
        } while (x != u);
    }
}

// 以dfs方式完成树形dp汇总
void dfs(int u) {
    // ① DP初始化
    // 对于以u为根的子树而言，如果剩余空间能够装得下u,那么最少将获取到V2[u]的价值
    for (int i = W2[u]; i <= m; i++) f[u][i] = V2[u];

    for (int i = h2[u]; ~i; i = ne[i]) {
        int v = e[i];
        dfs(v); // 先填充儿子，再回填充父亲

        // ② 有树形背包，有依赖的背包
        for (int i = m; i >= W2[u]; i--)                       // 枚举每个可能的空间
            for (int j = 0; j + W2[u] <= i; j++)               // 准备给v子树分配j这么大的空间
                f[u][i] = max(f[u][i], f[v][j] + f[u][i - j]); // 给v分配j这么大的空间，剩余就是一个子问题了
    }
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("NC19981.in", "r", stdin);
#endif
    memset(h1, -1, sizeof h1); // 初始人链式前向星
    memset(h2, -1, sizeof h2); // 初始人链式前向星
    scanf("%d%d", &n, &m);     // n个节点，m是最多能承受的重量上限
    // 体积，价值
    for (int i = 1; i <= n; i++) scanf("%d", W1 + i);
    for (int i = 1; i <= n; i++) scanf("%d", V1 + i);

    for (int i = 1; i <= n; i++) { // 枚举每个节点
        int x;                     // i依赖于x,由x->i建边
        scanf("%d", &x);
        if (x) add(h1, x, i); // x为0表示当前节点不需要前序依赖
    }

    // Tarjan缩点
    for (int i = 1; i <= n; i++)
        if (!dfn[i]) tarjan(i);

    // 枚举每条出边
    for (int u = 1; u <= n; u++)
        for (int i = h1[u]; ~i; i = ne[i]) {
            int v = e[i];
            int a = id[u], b = id[v];
            if (a != b) { // u和v不是同一个强连通分量，a-b之间创建边
                add(h2, a, b);
                in[b]++; // 标识强连通分量b的入度+1
            }
        }

    // 枚举每个强连通分量，找出入度为零的强连通分量,从虚拟源点0向这个入度为零的强连通分量引一条边
    for (int i = 1; i <= scc_cnt; i++)
        if (!in[i]) add(h2, 0, i);

    // 从超级源点出发，开始搜索
    dfs(0);

    // 从超级源点树的根0出发，分配容量最多为m时的最大价值
    printf("%d\n", f[0][m]);
    return 0;
}