对于软件的依赖可以转化为图上点之间的边的关系
发现对于一个强联通分量内的软件,一安则全安
Tarjan缩点
缩点后,从虚拟节点 0 向所有入度为 0 的点连边
这样就构成了一棵树
树形 dp
$dp[i][j]$ 表示对 $i$ 及其子树话费 $j$ 的价格所得到的收益
$dp[i][j] = dp[k][l] + dp[i][j - l]$

#include <bits/stdc++.h>

const int N = ;

int head[N], cnt;
struct Node {int u, v, nxt;};
int Tim, Bel[N], Low[N], Dfn[N], Stack[N], topp;
int W[N], V[N], Tw[N], Tv[N];
Node G[N];
int n, M;
bool vis[N];
int Gra; inline void Add(int u, int v) {G[++ cnt].v = v; G[cnt].nxt = head[u]; head[u] = cnt;} void Tarjan(int u) {
Dfn[u] = Low[u] = ++ Tim;
Stack[++ topp] = u, vis[u] = ;
for(int i = head[u]; ~ i; i = G[i].nxt) {
int v = G[i].v;
if(!Dfn[v]) {
Tarjan(v);
Low[u] = std:: min(Low[u], Low[v]);
} else if(vis[v]) Low[u] = std:: min(Low[u], Low[v]);
}
if(Low[u] == Dfn[u]) {
vis[u] = , Bel[u] = ++ Gra, Tw[Gra] += W[u], Tv[Gra] += V[u];
while(Stack[topp] != u) {
vis[Stack[topp]] = , Bel[Stack[topp]] = Gra, Tw[Gra] += W[Stack[topp]], Tv[Gra] += V[Stack[topp]];
topp --;
} topp --;
}
} int In[N], head_2[N];
Node E[N]; inline void Add2(int u, int v) {E[++ cnt].v = v, E[cnt].nxt = head_2[u], head_2[u] = cnt;} void Re_build() {
cnt = ;
for(int i = ; i <= Gra; i ++) head_2[i] = -;
for(int u = ; u <= n; u ++)
for(int i = head[u]; ~ i; i = G[i].nxt) {
int v = G[i].v;
if(Bel[u] != Bel[v]) Add2(Bel[u], Bel[v]), In[Bel[v]] = ;
}
} int f[N][N * ]; void Dfs(int u) {
for(int i = head_2[u]; ~ i; i = E[i].nxt) {
int v = E[i].v;
Dfs(v);
for(int j = M - Tw[u]; j >= ; j --)
for(int k = ; k <= j; k ++)
f[u][j] = std:: max(f[u][j], f[u][k] + f[v][j - k]);
}
for(int j = M; j >= ; j --) {
if(j >= Tw[u]) f[u][j] = f[u][j - Tw[u]] + Tv[u];
else f[u][j] = ;
}
} #define gc getchar() inline int read() {
int x = ; char c = gc;
while(c < '' || c > '') c = gc;
while(c >= '' && c <= '') x = x * + c - '', c = gc;
return x;
} int main() {
n = read(), M = read();
for(int i = ; i <= n; i ++) head[i] = -;
for(int i = ; i <= n; i ++) W[i] = read();
for(int i = ; i <= n; i ++) V[i] = read();
for(int i = ; i <= n; i ++) {
int u = read();
if(u) Add(u, i);
}
for(int i = ; i <= n; i ++) if(!Dfn[i]) Tarjan(i);
Re_build();
for(int i = ; i <= Gra; i ++) if(!In[i]) Add2(, i);
Dfs();
std:: cout << f[][M];
return ;
}

最新文章

  1. ROW_NUMBER() OVER的用法
  2. 安卓app中嵌入一个H5页面,当手机系统设置字体变大时,如何使H5页面的字体不会随用户自己调整的系统字体变化而变化?
  3. 术&amp;道
  4. 安装GRID时跑root.sh脚本报错(ORA-27091: unable to queue I/O)
  5. web开发workflow
  6. 【MySQL】源码编译安装和配置MySql 5.5.32(单实例)
  7. iOS开发——UI篇Swift篇&amp;UIToolbar
  8. UVa 1648 (推公式) Business Center
  9. C#+SQL数据库备份和还原
  10. C语言内存调试技巧—C语言最大难点揭秘
  11. BZOJ 2016: [Usaco2010]Chocolate Eating( 二分答案 )
  12. 使用Spring访问Mongodb的方法大全——Spring Data MongoDB查询指南
  13. Linux目录结构介绍-http://yangrong.blog.51cto.com/6945369/1288072
  14. hbase 迁库移库步骤
  15. F. Graph Without Long Directed Paths Codeforces Round #550 (Div. 3)
  16. Web开发相关笔记 #04# WebSocket
  17. pandas的时间戳
  18. Hexo站点之域名配置【2】
  19. MyEclipse10 Tomcat7关联
  20. mysql的TIMESTAMPDIFF

热门文章

  1. Nginx学习笔记(一):Nginx 进程模型 / 事件处理模型
  2. jacascript Date 学习
  3. 用python将项目中的所有代码(或txt)合并在一个文件中
  4. 面试经典算法:马拉松算法,最长回文子串Golang实现
  5. kong网关命令(一)
  6. Vue2.0+elementUI使用echarts插件
  7. dl pthread m库的含义
  8. Linux的awk 中的while do-while for循环
  9. mxnet在windows使用gpu 出错
  10. python3 基础三