BZOJ2427：[HAOI2010]软件安装—

https://www.lydsy.com/JudgeOnline/problem.php?id=2427

https://www.luogu.org/problemnew/show/P2515

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

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

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

dp简单题，然而因为数组开小了debug了两天？？？

（不过同时让我de出了一些题解的bug）

如果从属关系为环的话，显然其中一个选则全环都得选，于是tarjan缩点，变成了森林。

建虚点连接每个森林，剩余的就是树上背包了，与HDU1561：The more, The Better相同，但是因为n很小所以选择了O(n^2*m)的做法。

同时与那道题不同的是，因为体积可以为0，所以可能会出现有后效性的情况，特判之。

#include<map>

#include<stack>

#include<cstdio>

#include<vector>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

const int N=;

const int M=;

inline int read(){

    int X=,w=;char ch=;

    while(!isdigit(ch)){w|=ch=='-';ch=getchar();}

    while(isdigit(ch))X=(X<<)+(X<<)+(ch^),ch=getchar();

    return w?-X:X;

}

struct node{

    int to,nxt;

}e[N*];

stack<int>q;

bool inq[N];

int pre[N],d[N][N];

int cnt,head[N],n,m,dp[N][M];

int val[N],w[N],weight[N],b[N];

int dfn[N],low[N],to[N],indeg[N],t,l;

inline void add(int u,int v){

    e[++cnt].to=v;e[cnt].nxt=head[u];head[u]=cnt;

}

void dfs(int u){

    for(int i=b[u];i<=m;i++)dp[u][i]=w[u];

    for(int i=head[u];i;i=e[i].nxt){

        int v=e[i].to;

        dfs(v);

        for(int j=m;j>=b[u];j--){

            int tmp=dp[u][j];

            for(int k=b[u];k<=j-b[v];k++){

                if(k!=j)dp[u][j]=max(dp[u][j],dp[u][k]+dp[v][j-k]);

                else dp[u][j]=max(dp[u][j],tmp+dp[v][j-k]);

            }

        }

    }

}

void tarjan(int u){

    int v;

    dfn[u]=low[u]=++t;

    q.push(u);inq[u]=;

    for(int i=head[u];i;i=e[i].nxt){

        v=e[i].to;

        if(!dfn[v]){

            tarjan(v);

            low[u]=min(low[u],low[v]);

        }else if(inq[v])

            low[u]=min(low[u],dfn[v]);

    }

    if(dfn[u]==low[u]){

        l++;

        do{

            v=q.top();q.pop();

            inq[v]=;to[v]=l;

            w[l]+=val[v];b[l]+=weight[v];

        }while(v!=u);

    }

}

int main(){

    n=read(),m=read();

    for(int i=;i<=n;i++)weight[i]=read();

    for(int i=;i<=n;i++)val[i]=read();

    for(int v=;v<=n;v++){

        pre[v]=read();

        if(pre[v])add(pre[v],v);

    }

    for(int i=;i<=n;i++)

        if(!dfn[i])tarjan(i);

    memset(head,,sizeof(head));cnt=;

    for(int i=;i<=n;i++){

        int u=to[pre[i]],v=to[i];

        if(!pre[i]||u==v)continue;

        if(!d[u][v]){

            d[u][v]=;add(u,v);indeg[v]++;

        }

    }

    int rt=l+;

    for(int i=;i<=l;i++)

        if(!indeg[i])add(rt,i);

    dfs(rt);

    printf("%d\n",dp[rt][m]);

    return ;

}

+++++++++++++++++++++++++++++++++++++++++++

+本文作者：luyouqi233。　　　　　　　　　　　　　　+

+欢迎访问我的博客：http://www.cnblogs.com/luyouqi233/+

+++++++++++++++++++++++++++++++++++++++++++

巴特西

BZOJ2427：[HAOI2010]软件安装——题解

最新文章

热门文章