BZOJ 2427 [HAOI2010]软件安装 | 这道树形背包裸题严谨地证明了我的菜

时间：2023-03-10 06:12:48
BZOJ 2427 [HAOI2010]软件安装 | 这道树形背包裸题严谨地证明了我的菜

传送门

BZOJ 2427

题解

Tarjan把环缩成点，然后跑树形背包即可。

我用的树形背包是DFS序上搞的那种。

要注意dp数组初始化成-INF！

要注意dp顺推的时候也不要忘记看数组是否越界！

长太息以掩涕兮，

哀bug之难De...

#include <cstdio>

#include <cmath>

#include <cstring>

#include <algorithm>

#include <cstdlib>

#include <ctime>

using namespace std;

typedef long long ll;

#define enter putchar('\n')

#define space putchar(' ')

template <class T>

void read(T &x){

    char c;

    bool op = 0;

    while(c = getchar(), c > '9' || c < '0')

        if(c == '-') op = 1;

    x = c - '0';

    while(c = getchar(), c >= '0' && c <= '9')

        x = x * 10 + c - '0';

    if(op) x = -x;

}

template <class T>

void write(T x){

    if(x < 0) putchar('-'), x = -x;

    if(x >= 10) write(x / 10);

    putchar('0' + x % 10);

}

const int N = 105, M = 505, _INF = 0xc0c0c0c0;

int n, m, ans, _c[N], _w[N], c[N], w[N], fa[N], _adj[N], _nxt[N];

int dfn[N], low[N], idx, stk[N], top, bel[N], scc, cnt[N];

int adj[N], nxt[N], dp[N][M], sze[N], seq[N], tot;

bool ins[N];

void tarjan(int u){

    dfn[u] = low[u] = ++idx;

    stk[++top] = u, ins[u] = 1;

    for(int v = _adj[u]; v; v = _nxt[v])

        if(!dfn[v])

            tarjan(v), low[u] = min(low[u], low[v]);

        else if(ins[v])

            low[u] = min(low[u], dfn[v]);

    if(low[u] == dfn[u]){

        ++scc;

        int v = 0;

        while(v != u){

            ins[v = stk[top--]] = 0;

            bel[v] = scc, cnt[scc]++;

            c[scc] += _c[v], w[scc] += _w[v];

        }

    }

}

void rebuild(){

    static bool vis[N] = {0};

    for(int i = 1; i <= n; i++)

        if(cnt[bel[i]] > 1 && !vis[bel[i]])

            nxt[bel[i]] = adj[0], adj[0] = bel[i], vis[bel[i]] = 1;

        else if(cnt[bel[i]] == 1)

            nxt[bel[i]] = adj[bel[fa[i]]], adj[bel[fa[i]]] = bel[i];

}

void dfs(int u){

    seq[++tot] = u, sze[u] = 1;

    for(int v = adj[u]; v; v = nxt[v])

        dfs(v), sze[u] += sze[v];

}

int main(){

    read(n), read(m);

    for(int i = 1; i <= n; i++) read(_c[i]);

    for(int i = 1; i <= n; i++) read(_w[i]);

    for(int i = 1; i <= n; i++)

        read(fa[i]), _nxt[i] = _adj[fa[i]], _adj[fa[i]] = i;

    for(int i = 1; i <= n; i++)

        if(!dfn[i]) tarjan(i);

    rebuild();

    dfs(0);

    memset(dp, _INF, sizeof(dp));

    dp[1][0] = 0;

    for(int i = 1; i <= tot; i++){

        for(int j = 0; j <= m; j++){

            dp[i + sze[seq[i]]][j] = max(dp[i + sze[seq[i]]][j], dp[i][j]);

            if(j + c[seq[i]] <= m)

                dp[i + 1][j + c[seq[i]]] = max(dp[i + 1][j + c[seq[i]]], dp[i][j] + w[seq[i]]);

        }

    }

    for(int j = 0; j <= m; j++)

        ans = max(ans, dp[tot + 1][j]);

    write(ans), enter;

    return 0;

}

相关文章