[HAOI2010] 软件安装

题意

个软件和空间为 的硬盘,每个软件有一个占用空间 和价值 和一个依赖软件 表示没有依赖)。一个软件要安装,仅当其依赖软件已安装且硬盘空间足够,求最大价值.

.

分析

乍一眼树形 DP?

然而这 TM 可能是一个基环树森林

于是 tarjan 缩点,再树形 DP 即可

缩点之后,把森林中的每一棵树的根结点连到 0,方便 DP

以 i 为根的子树在容量为 j 的情况下考虑前 k 个子结点,i 本身取 / 不取的最大价值

设 i 的子结点序列为 .

这就是一维 0/1 背包,那么 倒序循环即可

目标: .

代码

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=220,M=510;
int n,m;
int w[N],v[N],d[N];

struct qxx{int nex,t;};
qxx e[N*4];
int h[N],cnt=1;
void add_path(int f,int t){e[++cnt]=(qxx){h[f],t},h[f]=cnt;}

int idx[N],cur;// 缩点后的编号
int dfn[N],low[N],dfncnt;
int s[N],tp,vis[N];
void tarjan(int u){
    dfn[u]=low[u]=++dfncnt,s[++tp]=u,vis[u]=1;
    for(int i=h[u];i;i=e[i].nex){const int &v=e[i].t;
        if(!dfn[v])tarjan(v),low[u]=min(low[u],low[v]);
        else if(vis[v])low[u]=min(low[v],dfn[v]);
    }
    if(low[u]==dfn[u]){
        ++cur;
        while(s[tp]!=u)vis[s[tp]]=0,idx[s[tp]]=cur,--tp;
        vis[s[tp]]=0,idx[s[tp]]=cur,--tp;
    }
}
int f[N][M];
void dp(int u){for(int i=h[u];i;i=e[i].nex)dp(e[i].t);
    for(int j=1;j<w[u];j++)f[u][j]=0;
    for(int j=w[u];j<=m;j++)f[u][j]=v[u];
    for(int i=h[u];i;i=e[i].nex){
        const int &v=e[i].t;
        for(int j=m;j>=w[u];j--){
            for(int p=w[u];p<=j;p++)f[u][j]=max(f[u][j],f[u][p]+f[v][j-p]);
        }
    }
}
int ind[N];// 入度
int main(){scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&w[i]);
    for(int i=1;i<=n;i++)scanf("%d",&v[i]);
    for(int i=1;i<=n;i++)scanf("%d",&d[i]),d[i]==0?0:(add_path(d[i],i),0);
    cur=n;// 避免与原图冲突
    for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i);
    for(int i=1;i<=n;i++)v[idx[i]]+=v[i],w[idx[i]]+=w[i];
    for(int i=1;i<=n;i++)if(d[i]&&idx[d[i]]!=idx[i])
        add_path(idx[d[i]],idx[i]),ind[idx[i]]++;
    for(int i=1+n;i<=cur;i++)if(!ind[i])add_path(0,i);
    dp(0);
    printf("%d",f[0][m]);
    return 0;
}

  转载请注明: Sshwy's Blog [HAOI2010] 软件安装

 上一篇
[SCOI2010] 股票交易 [SCOI2010] 股票交易
题意对于一个股市,给出第 天买 / 卖股票的价格和买 / 卖股票的数量,依次为 . 并要求手上的股票数不超过 ,两次交易的间隔时间至少 天(买卖都各算一次交易),初始时有
2019.01.16
下一篇 
[HAOI2011]Problem A [HAOI2011]Problem A
题意一次考试共有 个人参加,第 个人说:“有 个人分数比我高, 个人分数比我低。” 问最少有几个人没有说真话(可能有相同的分数) . 分
2019.01.16
  目录