首页 > 代码库 > bzoj2427 [HAOI2010]软件安装
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
tarjan缩完点树形背包dp
黄巨大说这种题很多但是我是第一次做啊……
#include<cstdio>#include<iostream>#include<cstring>#include<cstdlib>#include<algorithm>#include<cmath>#include<queue>#include<deque>#include<set>#include<map>#include<ctime>#define LL long long#define inf 0x7ffffff#define pa pair<int,int>#define pi 3.1415926535897932384626433832795028841971#define N 110#define M 510using namespace std;inline LL read(){ LL x=0,f=1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} return x*f;}inline void write(LL a){ if (a<0){printf("-");a=-a;} if (a>=10)write(a/10); putchar(a%10+‘0‘);}inline void writeln(LL a){write(a);printf("\n");}struct edge{int to,next;}e1[2*N],e2[2*N];int head1[N],head2[N];int c[N],w[N],fa[N],belong[N];int C[N],W[N],f[N][M];int dfn[N],low[N];int zhan[N],top;bool inset[N],mrk[N];int size[N];int n,m,cnt1,cnt2,cnt3,tt,ans;inline void ins1(int u,int v){ e1[++cnt1].to=v; e1[cnt1].next=head1[u]; head1[u]=cnt1;}inline void ins2(int u,int v){ e2[++cnt2].to=v; e2[cnt2].next=head2[u]; head2[u]=cnt2;}inline void dfs(int x){ low[x]=dfn[x]=++tt; zhan[++top]=x;inset[x]=1; for (int i=head1[x];i;i=e1[i].next) { if (!dfn[e1[i].to]) { dfs(e1[i].to); low[x]=min(low[x],low[e1[i].to]); }else if (inset[e1[i].to]) low[x]=min(low[x],dfn[e1[i].to]); } if (dfn[x]==low[x]) { cnt3++; int p=-1; while (p!=x) { p=zhan[top--]; inset[p]=0; belong[p]=cnt3; C[cnt3]+=c[p]; W[cnt3]+=w[p]; } }}inline void tarjan(){ for (int i=1;i<=n;i++) if (!dfn[i])dfs(i);}inline void treedp(int x){ if(mrk[x])return;mrk[x]=1; for (int i=head2[x];i;i=e2[i].next) if (!mrk[e2[i].to]) { treedp(e2[i].to); for (int j=m-C[x];j>=0;j--) for (int k=j;k>=0;k--) f[x][j]=max(f[x][j],f[x][j-k]+f[e2[i].to][k]); } for (int i=m;i>=0;i--) { if (i>=C[x]) f[x][i]=f[x][i-C[x]]+W[x]; else f[x][i]=0; }}int main(){ n=read();m=read(); for (int i=1;i<=n;i++)c[i]=read(); for (int i=1;i<=n;i++)w[i]=read(); for (int i=1;i<=n;i++) { fa[i]=read(); if (fa[i])ins1(fa[i],i); } tarjan(); for (int i=1;i<=n;i++) { for (int j=head1[i];j;j=e1[j].next) if (belong[e1[j].to]!=belong[i])ins2(belong[i],belong[e1[j].to]); } for (int i=1;i<=cnt3;i++)ins2(0,i); treedp(0); for (int i=0;i<=m;i++)ans=max(ans,f[0][i]); printf("%d\n",ans);}
bzoj2427 [HAOI2010]软件安装
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。