【BZOJ2427】[HAOI2010]软件安装 Tarjan+树形背包
2023-09-11 14:15:27 时间
【BZOJ2427】[HAOI2010]软件安装
Description
现在我们的手头有N个软件,对于一个软件i,它要占用Wi的磁盘空间,它的价值为Vi。我们希望从中选择一些软件安装到一台磁盘容量为M计算机上,使得这些软件的价值尽可能大(即Vi的和最大)。
但是现在有个问题:软件之间存在依赖关系,即软件i只有在安装了软件j(包括软件j的直接或间接依赖)的情况下才能正确工作(软件i依赖软件j)。幸运的是,一个软件最多依赖另外一个软件。如果一个软件不能正常工作,那么它能够发挥的作用为0。
我们现在知道了软件之间的依赖关系:软件i依赖软件Di。现在请你设计出一种方案,安装价值尽量大的软件。一个软件只能被安装一次,如果一个软件没有依赖则Di=0,这时只要这个软件安装了,它就能正常工作。
Input
第1行:N, M (0<=N<=100, 0<=M<=500)
第2行:W1, W2, ... Wi, ..., Wn (0<=Wi<=M )
第3行:V1, V2, ..., Vi, ..., Vn (0<=Vi<=1000 )
第4行:D1, D2, ..., Di, ..., Dn (0<=Di<=N, Di≠i )
Output
一个整数,代表最大价值。
Sample Input
3 10
5 5 6
2 3 4
0 1 1
5 5 6
2 3 4
0 1 1
Sample Output
5
题解:n个点n条边,所以依赖关系一定会出现环,环中的要么都取要么都不取,那么Tarjan缩环将环变成一个物品即可。然后原图就变成了森林,新建0号点将所有树根连起来然后跑树形背包即可。
#include <cstdio> #include <cstring> #include <iostream> using namespace std; int n,m,tot,sum,top,cnt,ans; int w[110],v[110],d[110],dep[110],low[110],ins[110],sta[110],bel[110],W[110],V[110],D[110]; int to[110],next[110],head[110],f[110][510],vis[110]; inline int rd() { int ret=0,f=1; char gc=getchar(); while(gc<'0'||gc>'9') {if(gc=='-')f=-f; gc=getchar();} while(gc>='0'&&gc<='9') ret=ret*10+gc-'0',gc=getchar(); return ret*f; } void tarjan(int x) { dep[x]=low[x]=++tot; ins[x]=1,sta[++top]=x; if(d[x]) { if(!dep[d[x]]) tarjan(d[x]),low[x]=min(low[x],low[d[x]]); else if(ins[d[x]]) low[x]=min(low[x],dep[d[x]]); } if(dep[x]==low[x]) { int t; sum++; do { t=sta[top--],bel[t]=sum,W[sum]+=w[t],V[sum]+=v[t],ins[t]=0; }while(t!=x); } } void add(int a,int b) { to[cnt]=b,next[cnt]=head[a],head[a]=cnt++; } void dfs(int x) { int i,j,k; for(i=0;i<W[x];i++) f[x][i]=-1<<29; f[x][W[x]]=V[x]; for(i=head[x];i!=-1;i=next[i]) { dfs(to[i]); for(j=m;j>=W[x]+W[to[i]];j--) for(k=W[to[i]];k<=j-W[x];k++) f[x][j]=max(f[x][j],f[x][j-k]+f[to[i]][k]); } } int main() { n=rd(),m=rd(); int i; for(i=1;i<=n;i++) w[i]=rd(); for(i=1;i<=n;i++) v[i]=rd(); for(i=1;i<=n;i++) d[i]=rd(); for(i=1;i<=n;i++) if(!dep[i]) tarjan(i); memset(head,-1,sizeof(head)); for(i=1;i<=n;i++) if(bel[d[i]]!=bel[i]) vis[bel[i]]=1,add(bel[d[i]],bel[i]); for(i=1;i<=sum;i++) if(!vis[i]) add(0,i); dfs(0); for(i=0;i<=m;i++) ans=max(ans,f[0][i]); printf("%d",ans); return 0; }
相关文章
- 记录一次成功的在centos8上安装jdk1.8
- Linux安装软件每次靠百度,这次花了些时间,终于算是搞明白了
- Ubuntu下软件安装的几种方式,apt,dpkg工具的使用
- 使用virtualbox安装的Ubuntu,窗口分辨率过小,使用增强工具完成和vmtools一样的功能。
- 通过yum方式安装软件
- Mac 安装第三方软件遇到的问题解决方案汇总
- 从0开始玩转docker—— 01软件安装
- OpenEuler安装xfce桌面 及 远程桌面软件xrdp
- 在linux上安装运行安卓系统
- 【Linux操作系统】如何实现Linux中软件安装进度条?
- 安装、使用ssh服务详解
- Docker 安装 建木CI
- Windows上安装配置SSH教程(2)——在Windows XP和Windows 10上安装并配置OpenSSH for Windows
- 系统环境出现问题,安装zabbix-server报错nothing provides libiksemel.so.3()(64bit) needed by zabbix-server-mysql-4.0.0-2.el7.x86_64
- CentOS安装错误:no default or ui configuration
- 用yum查询想安装的软件
- Linux如何用yum安装软件或服务
- VM10虚拟机安装图解
- 【正点原子FPGA连载】第四章Quartus II软件的安装和使用 -摘自【正点原子】新起点之FPGA开发指南_V2.1
- 常用开发工具 之 MySql 数据库的开始画操作界面软件 Workench下载与安装
- 微软:全球Win10企业安装量超过5000万
- Apple M1 上安装tensorflow开发环境
- 一个命令清理电脑垃圾,不用再安装任何管家软件,节省电脑资源,让电脑运行更快更流畅
- PC软件安装量排名出炉:最高的竟是它
- 数据库系统原理课程总结1——基本概念,业务背景,ER图,完整性约束,MySQL软件安装