锐客网

  1. 首页 > it技术 > >

2017NOIP模拟赛|2017NOIP模拟赛 软件安装（tarjan缩点+树形dp）

问题描述

【2017NOIP模拟赛|2017NOIP模拟赛 软件安装（tarjan缩点+树形dp）】现在我们的手头有N个软件，对于一个软件i，它要占用Wi的磁盘空间，它的价值为Vi。我们希望从中选择一些软件安装到一台磁盘容量为M的计算机上，使得这些软件的价值尽可能大（即Vi的和最大）。
但是现在有个问题：软件之间存在依赖关系，即软件i只有在安装了软件j（包括软件j的直接或间接依赖）的情况下才能正确工作（软件吗i依赖软件j）。幸运的是，一个软件最多依赖另外一个软件。如果一个软件不能正常工作，那么他能够发挥的作用为0。
我们现在知道了软件之间的依赖关系：软件i依赖Di。现在请你设计出一种方案，安装价值尽量大的软件。一个软件只能被安装一次，如果一个软件没有依赖则Di=0，这是只要这个软件安装了，它就能正常工作。
输入格式
第1行：N,M （0<=N<=100,0<=M<=500） 第2行：W1,W2, … Wi, … ,Wn 第3行：V1,V2, … Vi,
… ,Vn 第4行：D1,D2, … Di, … ,Dn
输出格式
一个整数，代表最大价值。
样例输入 3 10
5 5 6
2 3 4
0 1 1
样例输出 5
题解 tarjan缩点+树形dp
代码
#include #include #include #include #include #include #include #include using namespace std; #define maxn 105 int n,m; bool instack[maxn]; stacks; int w[maxn],v[maxn],d[maxn]; int w1[maxn],v1[maxn]; int dfn[maxn],low[maxn]; int be[maxn]; int vt,scc; int st[maxn]; int End1[maxn],End2[maxn],Next1[maxn],Next2[maxn],Last1[maxn],Last2[maxn]; int ru[maxn]; int dp[101][505]; void tj(int x) { int i,j,k; dfn[x]=low[x]=++vt; instack[x]=true; s.push(x); for(i=Last1[x]; i; i=Next1[i]) { int en=End1[i]; if(!dfn[en]){ tj(en); low[x]=min(low[x],low[en]); } else if(instack[en]){ low[x]=min(dfn[en],low[x]); } } int t; if(dfn[x]==low[x]){ scc++; do{ t=s.top(); s.pop(); be[t]=scc; w1[scc]+=w[t]; v1[scc]+=v[t]; instack[t]=false; }while(t!=x); } } void dpp(int x) { int i,j,k; for(k=Last2[x]; k; k=Next2[k]) { int en=End2[k]; dpp(en); for(i=m-w1[x]; i>=1; i--) { for(j=1; j<=i; j++) { dp[x][i]=max(dp[x][i],dp[x][i-j]+dp[en][j]); } } }for(k=m; k>=0; k--) { if(k>=w1[x]) dp[x][k]=dp[x][k-w1[x]]+v1[x]; else dp[x][k]=0; }} int cnt; void insert(int x,int y) { Next1[++cnt]=Last1[x]; st[cnt]=x; Last1[x]=cnt; End1[cnt]=y; } void insert2(int x,int y) { Next2[++cnt]=Last2[x]; Last2[x]=cnt; End2[cnt]=y; } int main() { int i,j,k; scanf("%d%d",&n,&m); for(i=1; i<=n; i++) scanf("%d",&w[i]); for(i=1; i<=n; i++) scanf("%d",&v[i]); for(i=1; i<=n; i++) { int x; scanf("%d",&d[i]); if(d[i]) insert(d[i],i); } for(i=1; i<=n; i++) if(!dfn[i]) tj(i); int num1=cnt; cnt=0; for(i=1; i<=num1; i++){ int x=be[st[i]],y=be[End1[i]]; if(x!=y){ //cout<

    推荐阅读


    上一篇：jsoup|jsoup中选择器select()的使用（jquery,css选择器风格）

    下一篇：CPU占用2%-