首页 > 代码库 > 【BZOJ-2427】软件安装 Tarjan + 树形01背包
【BZOJ-2427】软件安装 Tarjan + 树形01背包
2427: [HAOI2010]软件安装
Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 960 Solved: 380
[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
5 5 6
2 3 4
0 1 1
Sample Output
5
HINT
Source
Day2
Solution
把环缩成一个点...
建立超级根0....
然后树形01背包
Code
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>using namespace std;inline int read(){ int 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;}#define MAXN 110#define MAXM 510struct EdgeNode{int next,to;}edge[MAXN<<1],road[MAXN<<1];int head[MAXN],cnt=1,first[MAXN],tot=1;inline void AddEdge(int u,int v) {cnt++; edge[cnt].next=head[u]; head[u]=cnt; edge[cnt].to=v;}inline void InsertEdge(int u,int v) {if (!u) return; AddEdge(u,v);}int w[MAXN],v[MAXN],V[MAXN],W[MAXN],N,M;int dfn[MAXN],low[MAXN],st[MAXN],top,visit[MAXN],belong[MAXN],size[MAXN],dfsn,scc;inline void Tarjan(int x){ dfn[x]=low[x]=++dfsn; visit[x]=1; st[++top]=x; for (int i=head[x]; i; i=edge[i].next) if (!dfn[edge[i].to]) Tarjan(edge[i].to),low[x]=min(low[x],low[edge[i].to]); else if (visit[edge[i].to]) low[x]=min(dfn[edge[i].to],low[x]); if (dfn[x]==low[x]) { int stp=0; scc++; while (x!=stp) stp=st[top--],size[scc]++,W[scc]+=w[stp],V[scc]+=v[stp],belong[stp]=scc,visit[stp]=0; }}inline void AddRoad(int u,int v) {tot++; road[tot].next=first[u]; first[u]=tot; road[tot].to=v;}inline void InsertRoad(int u,int v) {AddRoad(u,v); AddRoad(v,u);}bool flag[MAXN];inline void Rebuild(){ for (int i=1; i<=N; i++) for (int j=head[i]; j; j=edge[j].next) if (belong[i]!=belong[edge[j].to]) InsertRoad(belong[i],belong[edge[j].to]),flag[belong[edge[j].to]]=1; for (int i=1; i<=scc; i++) if (!flag[i]) InsertRoad(0,i);}int f[MAXN][MAXM],g[MAXN][MAXM];void DP(int x,int last){ for (int i=first[x]; i; i=road[i].next) if (road[i].to!=last) { DP(road[i].to,x); for (int j=M-W[x]; j>=0; j--) for (int k=0; k<j; k++) g[x][j]=max(g[x][j],g[x][k]+f[road[i].to][j-k]); } for (int i=0; i<=M-W[x]; i++) f[x][i+W[x]]=g[x][i]+V[x];}int main(){ N=read(),M=read(); for (int i=1; i<=N; i++) w[i]=read(); for (int i=1; i<=N; i++) v[i]=read(); for (int f,i=1; i<=N; i++) f=read(),InsertEdge(f,i); for (int i=1; i<=N; i++) if (!dfn[i]) Tarjan(i); Rebuild(); DP(0,0); printf("%d\n",f[0][M]); return 0;}
【BZOJ-2427】软件安装 Tarjan + 树形01背包
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。