[BZOJ2427]&&[HAOI2010] 软件安装

描述 Description

现在我们的手头有 N 个软件,对于一个软件 i,它要占用 Wi 的磁盘空间,它的价值为 Vi。我们希望从中选择一些软件安装到一台磁盘容量为 M 计算机上,使得这些软件的价值尽可能大(即 Vi 的和最大)。

但是现在有个问题:软件之间存在依赖关系,即软件 i 只有在安装了软件 j(包括软件 j 的直接或间接依赖)的情况下才能正确工作(软件 i 依赖软件 j)。幸运的是,一个软件最多依赖另外一个软件。如果一个软件不能正常工作,那么它能够发挥的作用为 0。

我们现在知道了软件之间的依赖关系:软件 i 依赖软件 Di。现在请你设计出一种方案,安装价值尽量大的软件。一个软件只能被安装一次,如果一个软件没有依赖则 Di=0,这时只要这个软件安装了,它就能正常工作。

输入格式 InputFormat

第 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 )

输出格式 OutputFormat

一个整数,代表最大价值。

样例输入 SampleInput

3 10
5 5 6
2 3 4
0 1 1

样例输出 SampleOutput

5


BZOJ 2427


我们考虑到这题有可能存在有环的情况,而对于依赖关系构成的环要么都要要么都不要,于是可以 Floyd 或者 tarjan 缩点,然后就是和选课一样的树形动规了。

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn=105;
const int maxm=505;
int i,j,t,n,m,l,r,k,z,y,x;
struct node
{
    int fa,b,c;
}a[maxn];
int w[maxn],v[maxn],d[maxn],c[maxn];
bool b[maxn][maxn];
int f[maxn][maxm];
inline void merge(int x,int y)
{
    if (x!=y && b[x][y] && b[y][x] && !c[x] && !c[y])
    {
        v[++n]=v[x]+v[y];w[n]=w[x]+w[y];
        c[x]=c[y]=n;
    }
    if (b[y][d[y]] && b[d[y]][y] && !c[y] && c[d[y]])
    {
        w[c[d[y]]]+=w[y];v[c[d[y]]]+=v[y];
        c[y]=c[d[y]];
    }
    if (c[d[y]] && !c[y] && ((b[y][d[y]] && !b[d[y]][y]) || (b[d[y]][y] && !b[y][d[y]])))
    {
        d[y]=c[d[y]];
    }
}
inline void mkt(int s)
{
    a[s].b=a[d[s]].c;
    a[d[s]].c=s;
}
int dfs(int s,int k)
{
    int i,j,t;
    if (f[s][k]>0) return f[s][k];
    if (s==0 || k<=0) return 0;
    f[s][k]=f[a[s].b][k]=dfs(a[s].b,k);
    t=k-w[s];
    for (i=0;i<=t;i++)
    {
        f[a[s].c][t-i]=dfs(a[s].c,t-i);
        f[a[s].b][i]=dfs(a[s].b,i);
        f[s][k]=max(f[s][k],v[s]+f[a[s].b][i]+f[a[s].c][t-i]);
    }
    return f[s][k];
}
int main()
{
    memset(b,0,sizeof(b));
    memset(c,0,sizeof(c));
    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++) scanf("%d",&d[i]),b[d[i]][i]=1;
    for (k=1;k<=n;k++) for (i=1;i<=n;i++) for (j=1;j<=n;j++) b[i][j]=b[i][j] | b[i][k]&b[k][j];
    for (i=1;i<=n;i++) for (j=1;j<=n;j++) merge(i,j);
    for (i=1;i<=n;i++) if (!c[i]) mkt(i);
    printf("%d\n",dfs(a[0].c,m));
    return 0;
}