洛谷题单指南-树与图上的动态规划-P2515 [HAOI2010] 软件安装

原题链接：https://www.luogu.com.cn/problem/P2515

题意解读：在一个非联通图中，每个点有体积有价值，求选取不超过m体积的节点的最大价值，选择一个点必须选择其父节点。

解题思路：

由于是非联通图，又由于有可能存在环，而环中任选一个点其他所有点都要选。

因此，可以先用tarjan缩点，缩点的体积、价值是环中所有点的体积、价值之和。

由于不一定连通，建立一个虚拟0点作为根节点，指向所有入度为0的缩点，这样就得到一棵树。

这时，问题就变成了有依赖的背包问题。

1、状态表示

设f[i][j]表示以i为根的子树中总体积不超过j的节点最大价值和。

W[N],V[N]分别是缩点之后的体积、价值

2、状态转移

设根节点u

先枚举u的所有子树v

再枚举在u的子树中选择的体积最大值i:：m ~ W[u]，因为u必选，体积至少是W[u]

最后枚举在子树v中选择的体积j：0 ~ i - W[u]，因为要空出u的体积

f[u][i] = max(f[u][i], f[v][j] + f[u][i - j]);

3、初始化

for(inti=W[u]; i<=m; i++) f[u][i] =V[u];
4、结果

f[0][m]
100分代码：

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

const int N = 105, M = 505;
int w[N], v[N], d[N];
int dfn[N], low[N], timestamp;
stack<int> stk;
bool vis[N];
int scc[N], cnt;
int W[N], V[N];
int SW[N], SV[N], idx;
vector<int> g1[N], g2[N]; //原图，缩点图
int in[N]; //缩点的入度
int f[N][M];
int n, m;

void tarjan(int u)
{
    dfn[u] = low[u] = ++timestamp;
    stk.push(u);
    vis[u] = true;

    for(auto to : g1[u])
    {
        if(!dfn[to])
        {
            tarjan(to);
            low[u] = min(low[u], low[to]);
        }
        else if(vis[to]) low[u] = min(low[u], dfn[to]);
    }

    if(low[u] == dfn[u])
    {
        cnt++;
        while (true)
        {
            int t = stk.top(); stk.pop();
            vis[t] = false;
            scc[t] = cnt;
            W[cnt] += w[t];
            V[cnt] += v[t];
            if(t == u) break;
        }
    }
}

void dfs(int u)
{
    for(int i = W[u]; i <= m; i++) f[u][i] = V[u];

    int sz = 1;
    for(auto v : g2[u])
    {
        dfs(v);

        for(int i = m; i >= W[u]; i--) //以u为根的子树，容量至少是W[u]
            for(int j = 0; j <= i - W[u]; j++) //以v为根的子树，容量不能超过i - w[u]
                f[u][i] = max(f[u][i], f[v][j] + f[u][i - j]);
    }
}

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> w[i];
    for(int i = 1; i <= n; i++) cin >> v[i];
    for(int i = 1; i <= n; i++) 
    {
        cin >> d[i];
        if(d[i]) g1[d[i]].push_back(i);
    }

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

    for(int u = 0; u <= n; u++)
    {
        for(auto v : g1[u])
        {
            int a = scc[u], b = scc[v];
            if(a != b) 
            {
                g2[a].push_back(b);
                in[b]++;
            }
        }
    }

    for(int i = 1; i <= cnt; i++) //建立虚拟根节点，指向所有入度为0的节点
        if(in[i] == 0) 
            g2[0].push_back(i);

    dfs(0);
    cout << f[0][m];
    return 0;
}