P2515 [HAOI2010] 软件安装

题目

P2515 [HAOI2010] 软件安装

算法标签: 树形$dp$, $Tarjan$算法求强连通分量, 树上背包

思路

发现可能存在互相依赖的情况, 可以使用$Tarjan$算法将互相依赖的视为一个点进行缩点, 然后在新的拓扑图上跑树上背包 , 创建虚拟源点, 将所有$scc$连接, 然后在此基础上进行动态规划

代码

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 110, M = 1010;

int n, m, w[N], v[N];
int head1[N], head2[N], ed[M], ne[M], idx;
int dfn[N], low[N], timestamp;
int scc_cnt, id[N], stk[N], top;
bool in_stk[N];
int scc_w[N], scc_v[N];
int deg[N];
int f[N][M];

void add(int head[], int u, int v) {
   
    ed[idx] = v, ne[idx] = head[u], head[u] = idx++;
}

void tarjan(int u) {
   
    dfn[u] = low[u] = ++timestamp;
    stk[++top] = u, in_stk[u] = true;
    for (int i = head1[u]; ~i; i = ne[i]) {
   
        int v = ed[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 ver;
        do {
   
            ver = stk[top--];
            in_stk[ver] = false;
            id[ver] = scc_cnt;
            scc_w[scc_cnt] += w[ver], scc_v[scc_cnt] += v[ver];
        } while (ver != u);
    }
}

void dfs(int u) {
   
    for (int j = scc_v[u]; j <= m; ++j) {
   
        f[u][j] = scc_w[u];
    }

    for (int i = head2[u]; ~i; i = ne[i]) {
   
        int v = ed[i];
        dfs(v);
        for (int j = m; j >= scc_v[u]; --j) {
   
            for (int k = 0; k <= j - scc_v[u]; ++k) {
   
                f[u][j] = max(f[u][j], f[u][j - k] + f[v][k]);
            }
        }
    }
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    memset(head1, -1, sizeof head1);
    memset(head2, -1, sizeof head2);

    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> v[i];
    for (int i = 1; i <= n; ++i) cin >> w[i];

    for (int i = 1; i <= n; ++i) {
   
        int fa;
        cin >> fa;
        if (fa) add(head1, fa, i);
    }

    for (int i = 1; i <= n; ++i) {
   
        if (!dfn[i]) tarjan(i);
    }

    for (int u = 1; u <= n; ++u) {
   
        for (int i = head1[u]; ~i; i = ne[i]) {
   
            int v = ed[i];
            int scc1 = id[u], scc2 = id[v];
            if (scc1 != scc2) {
   
                add(head2, scc1, scc2);
                deg[scc2]++;
            }
        }
    }

    // 将单独的结点连接到0号点上
    for (int i = 1; i <= scc_cnt; ++i) {
   
        if (!deg[i]) add(head2, 0, i);
    }

    dfs(0);

    cout << f[0][m] << "\n";
    return 0;
}