洛谷 P2515 软件安装 —— tarjan + 树形背包

本文主要是介绍洛谷 P2515 软件安装 —— tarjan + 树形背包，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：点我啊╭(╯^╰)╮

题目大意：

    每个点有重量、价值、依赖点
    树形背包模型，求体积为 $M$ 的背包的最大值

解题思路：

    注意根据依赖点建图后不是树和森林
    因为会形成环，环上的点要么都选，要么都不选
    因此 $tarjan$ 缩点后跑一下树形背包即可
    这里用了 $dfs$ 序的 $O(nw)$ 算法
    $namo$ 为什么 P2014 [CTSC1997]选课 这道题就是森林而不会形成环呢？
    注意数组越界报wa会多折腾几个小时

#include<bits/stdc++.h>
#define rint register int
#define deb(x) cerr<<#x<<" = "<<(x)<<'\n';
using namespace std;
typedef long long ll;
typedef pair <int,int> pii;
const int maxn = 2e3 + 5;
int n, m, d[maxn], w[maxn], v[maxn]; 
int nw[maxn], nv[maxn], nw2[maxn], nv2[maxn];
int dfn[maxn], low[maxn], vis[maxn], col[maxn];
int s[maxn], top, tot, numc, nxt[maxn];
int dp[maxn][505], in[maxn];
vector <int> g[maxn];void tarjan(int u){dfn[u] = low[u] = ++tot;s[++top] = u;vis[u] = 1;for(auto v : g[u]){if(!dfn[v]){tarjan(v);low[u] = min(low[u], low[v]);} else if(vis[v]) low[u] = min(low[u], dfn[v]);}if(dfn[u] == low[u]){++numc;while(s[top+1] ^ u){col[s[top]] = numc;nw[numc] += w[s[top]]; nv[numc] += v[s[top]]; vis[s[top--]] = 0;}}
}void dfs(int u){dfn[u] = tot++;for(auto v : g[u]) dfs(v);nxt[dfn[u]] = tot;
}signed main() {scanf("%d%d", &n, &m);for(int i=1; i<=n; i++) scanf("%d", w+i);for(int i=1; i<=n; i++) scanf("%d", v+i);for(int i=1; i<=n; i++) {scanf("%d", d+i);if(d[i]) g[d[i]].push_back(i);}for(int i=1; i<=n; i++)if(!dfn[i]) tarjan(i);for(int i=0; i<=n; i++) g[i].clear();for(int i=1; i<=n; i++)if(col[i] ^ col[d[i]] && d[i]) g[col[d[i]]].push_back(col[i]), in[col[i]]++;for(int i=1; i<=numc; i++)if(!in[i]) g[0].push_back(i);dfs(tot = 0);memset(dp, 128, sizeof(dp));memset(dp[0], 0, sizeof(dp[0]));for(int i=1; i<=numc; i++) nw2[dfn[i]] = nw[i];for(int i=1; i<=numc; i++) nv2[dfn[i]] = nv[i];for(int i=0; i<=numc; i++)for(int j=0; j<=m; j++){dp[nxt[i]][j] = max(dp[nxt[i]][j], dp[i][j]);if(j + nw2[i] > m) continue; dp[i+1][j+nw2[i]] = max(dp[i+1][j+nw2[i]], dp[i][j] + nv2[i]);}printf("%d\n", dp[numc+1][m]);
}

这篇关于洛谷 P2515 软件安装 —— tarjan + 树形背包的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---