「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
Sample Output
5
题解
显然图是一些环和树
若有环必须选整个环，或者直接舍弃
将环缩点完之后变成一堆点和森林，建立虚点向所有无入度的点连边
缩点用闭包传递或者tarjan，剩下的就是个树形dp问题T T
f(i,j)表示对i及其子树花费j代价产生的最大价值
转移略
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 |
#include<iostream> #include<cstdio> #include<cstdlib> #include<algorithm> #include<cmath> #include<cstring> #define inf 2000000000 #define ll long long 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; } int n,m,cnt,scc,ind,top; int v[105],w[105]; int sv[105],sw[105]; int dfn[105],low[105],belong[105]; int q[105],f[105][505],in[505]; struct edge{ int to,next; }e[505],ed[505];int last[105],last2[105]; bool inq[105]; void insert(int u,int v) { e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt; } void insert2(int u,int v) { in[v]=1; ed[++cnt].to=v;ed[cnt].next=last2[u];last2[u]=cnt; } void tarjan(int x) { int now=0; low[x]=dfn[x]=++ind; q[++top]=x;inq[x]=1; for(int i=last[x];i;i=e[i].next) if(!dfn[e[i].to]) { tarjan(e[i].to); low[x]=min(low[x],low[e[i].to]); } else if(inq[e[i].to]) low[x]=min(low[x],dfn[e[i].to]); if(low[x]==dfn[x]) { scc++; while(now!=x) { now=q[top--];inq[now]=0; belong[now]=scc; sv[scc]+=v[now]; sw[scc]+=w[now]; } } } void rebuild() { cnt=0; for(int x=1;x<=n;x++) for(int i=last[x];i;i=e[i].next) if(belong[e[i].to]!=belong[x]) insert2(belong[x],belong[e[i].to]); } void dp(int x) { for(int i=last2[x];i;i=ed[i].next) { dp(ed[i].to); for(int j=m-sw[x];j>=0;j--) { for(int k=0;k<=j;k++) f[x][j]=max(f[x][j],f[x][k]+f[ed[i].to][j-k]); } } for(int j=m;j>=0;j--) { if(j>=sw[x])f[x][j]=f[x][j-sw[x]]+sv[x]; else f[x][j]=0; } } int main() { freopen("install.in","r",stdin); freopen("install.out","w",stdout); 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 i=1;i<=n;i++) { int x=read(); if(x)insert(x,i); } for(int i=1;i<=n;i++) if(!dfn[i])tarjan(i); rebuild(); for(int i=1;i<=scc;i++) if(!in[i]) insert2(scc+1,i); dp(scc+1); printf("%d\n",f[scc+1][m]); return 0; } |
计数器 9854176
OI 课件=>
OI 课件=>
黄学长，您的代码好像有问题，提供一组测试数据
4 10
0 2 4 3
1 3 2 2
2 0 3 0
输出应为8，但您的输出为9
Orz！
75行的for(int k=0;k<=j;k++)
j递增应该改为j递减，因为W有可能为0
Orz KPM！