[BZOJ2427][HAOI2010]软件安装(Tarjan+DP)
2427: [HAOI2010]软件安装
Time Limit: 10 SecMemory Limit: 128 MBSubmit: 1987Solved: 791
[Submit][Status][Discuss]
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
Sample Output
5
HINT
Source
Day2
这么简单的题竟然做了三个小时?
环套树DP,为了方便直接Tarjan缩点然后跑树形DP即可。至于多叉树转二叉树这个方法完全不需要用上,直接做树上背包即可。
注意:除非卡常时,不要再用~i表示i>=0了,这样无法处理i<0的情况。
坚决避免低级错误!
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #define rep(i,l,r) for (int i=l; i<=r; i++) 5 #define For(i,x) for (int i=h[x]; i; i=nxt[i]) 6 using namespace std; 7 8 const int N=2100; 9 int n,m,scc,cnt,tim,top,h[N<<1],ind[N],w[N],v[N],d[N],wei[N],val[N]; 10 int bel[N],dp[N][N],stk[N],inq[N],dfn[N],low[N],to[N<<2],nxt[N<<2]; 11 12 void add(int u,int v){ to[++cnt]=v; nxt[cnt]=h[u]; h[u]=cnt; } 13 14 void tarjan(int x){ 15 low[x]=dfn[x]=++tim; inq[x]=1; stk[++top]=x; 16 For(i,x){ 17 int k=to[i]; 18 if (!dfn[k]) tarjan(k),low[x]=min(low[x],low[k]); 19 else if (inq[k]) low[x]=min(low[x],dfn[k]); 20 } 21 if (dfn[x]==low[x]){ 22 int t; scc++; 23 do{ t=stk[top--]; inq[t]=0; bel[t]=scc; }while (t!=x); 24 } 25 } 26 27 void dfs(int x){ 28 rep(i,wei[x],m) dp[x][i]=val[x]; 29 For(i,x){ 30 int k=to[i]; dfs(k); 31 for (int j=m-wei[x]; j>=0; j--) 32 rep(q,0,j) 33 dp[x][j+wei[x]]=max(dp[x][j+wei[x]],dp[x][j+wei[x]-q]+dp[k][q]); 34 } 35 } 36 37 int main(){ 38 scanf("%d%d",&n,&m); scc=n; 39 rep(i,1,n) scanf("%d",&w[i]); 40 rep(i,1,n) scanf("%d",&v[i]); 41 rep(i,1,n) { scanf("%d",&d[i]); if (d[i]) add(d[i],i); } 42 rep(i,1,n) if (!dfn[i]) tarjan(i); 43 rep(i,1,n){ 44 wei[bel[i]]+=w[i]; val[bel[i]]+=v[i]; 45 if (bel[i]!=bel[d[i]] && d[i]) add(bel[d[i]],bel[i]),ind[bel[i]]++; 46 } 47 rep(i,n+1,scc) if (!ind[i]) add(scc+1,i); 48 dfs(scc+1); printf("%d\n",dp[scc+1][m]); 49 return 0; 50 }
相关推荐
86417413 2020-11-25
83206733 2020-11-19
86276537 2020-11-19
83266337 2020-11-19
86256434 2020-11-17
zhouboxiao 2020-11-16
rise 2020-11-22
sssdssxss 2020-11-20
windle 2020-11-10
孙雪峰 2020-10-30
85477104 2020-11-17
xfcyhades 2020-11-20
liuxudong00 2020-11-19
cheidou 2020-11-19
gunhunti 2020-09-25
csdnYF 2020-11-15
达观数据 2020-11-11
playlinuxxx 2020-11-11