P2515 [HAOI2010]软件安装 题解


以下题解仅供学习参考使用。

抄袭、复制题解,以达到刷AC率/AC数量或其他目的的行为,在洛谷是严格禁止的。

洛谷非常重视学术诚信。此类行为将会导致您成为作弊者。具体细则请查看洛谷社区规则

评论

  • Simpson561
    错别字……
  • 杨铠远
    建议置顶!!!
作者: 凤睚 更新时间: 2017-10-26 15:58  在Ta的博客查看 举报    17  

下面的题解说得很好了,但是有一点非常重要且容易忽视!!

见图的时候是从Di向i建一条有向边,,重新建图的时候是从color[d[i]]向color[i]建边

原因:因为i依赖Di,所以dfs时,应先安装了(即遍历了)Di才能安装i,重新建图后一样。

代码(重新建图时和其他题解稍有区别):

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=2005;
int map[N][N],w[N],v[N],x[N],y[N],head[N],k=0,low[N],sta[N],top=0,dfn[N],tim=0,color[N],color_time=0,n,m,rd[N],dp[N][N],wei[N],val[N];
bool vis[N];
struct node
{
    int to,next,w;
}edge[N*4];
void add(int u,int v)
{
    edge[++k].to=v;
    edge[k].next=head[u];
    head[u]=k;
}
void tarjan(int x)
{
    low[x]=dfn[x]=++tim;
    sta[++top]=x;vis[x]=1;
    for(int i=head[x];i;i=edge[i].next)
    {
        if(!dfn[edge[i].to])tarjan(edge[i].to),low[x]=min(low[x],low[edge[i].to]);
        else if(vis[edge[i].to])low[x]=min(low[x],dfn[edge[i].to]);
    }
    if(dfn[x]==low[x])
    {
        ++color_time;
        vis[x]=false;
        while(sta[top+1]!=x)
        {
            color[sta[top]]=color_time;
            vis[sta[top--]]=false;
        }
    }
}
void dfs(int x)
{
    for(int i=wei[x];i<=m;i++)dp[x][i]=val[x];
    for(int i=head[x];i;i=edge[i].next)
    {
        dfs(edge[i].to);
        for(int j=m-wei[x];j>=0;j--)
        {
            for(int q=0;q<=j;q++)
            {
                dp[x][j+wei[x]]=max(dp[x][j+wei[x]],dp[x][j+wei[x]-q]+dp[edge[i].to][q]);
            }
        }
    }
}
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",&y[i]);
        if(y[i]==0)continue;
        add(y[i],i);//此处注意
    }
    for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i);
    memset(edge,0,sizeof(edge));
    memset(head,0,sizeof(head));
    k=0;
    for(int i=1;i<=n;i++)
    {
        val[color[i]]+=v[i];wei[color[i]]+=w[i];
        if(color[i]!=color[y[i]]&&y[i]!=0)
        add(color[y[i]],color[i]),rd[color[i]]++;//此处注意
    }
    for(int i=1;i<=color_time;i++)
    if(rd[i]==0)add(color_time+1,i);
    dfs(color_time+1);
    printf("%d",dp[color_time+1][m]);
}

评论

  • xuezha
    dalao能问下为什么不能一开始就让他们和0建边?qwq
  • AcFirmament
    怎么图又没了啊。。。。。。。。。。
  • AcFirmament
    抱歉图找不到了。。
  • 小略
    errr
  • 小略
    %%%
  • Chaos1018
    STO ORZ
  • AcFirmament
    ????图又回来了。。。
  • Boeing777X
    ????图又回来了。。。
  • ghj1222
    ????图又失踪了。。。
  • yyc001
    ????图又失踪了。。。
作者: AcFirmament 更新时间: 2018-07-26 18:31  在Ta的博客查看 举报    12  

Description

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

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

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

Solution

明显是树形dp。设$dp[i][j]$为以$i$号点为根的子树中用不超过$j$的空间的最大价值。

但是这道题所给出的条件不能直接构成一棵树,比如$d[1]=2,d[2]=3,d[3]=1$这时$1,2,3$便形成一个独立的联通块并且构成环。又由于这个环也很特殊:要么都选,要么都不选,所以可以用tarjan将环缩点。新点的$w=\sum\limits_{e \in \text{该环}}w[e]$,$v=\sum\limits_{e \in \text{该环}}v[e]$。

缩点后将原来的联通块之间的边连好后再从$0$向每一个加完边后入度为$0$的点连一条边,此时就将原图转换为一颗以$0$为根的树,然后就可以愉快的树形dp辣。

举个栗子:

如果最开始图是这样的

然后缩点,将$1,2,3$缩为$14$,$10,11,12,13$缩为$15$,然后让$0$向几个联通块连边:

这时原图被转换成对答案等价的一棵树,然后$dfs$用上述方程进行简单的树上背包就解决了。

code

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>

using namespace std;
const int MAXN = 505;
int n, m, cnt, w[MAXN], a[MAXN], d[MAXN]; 
int dfn[MAXN], low[MAXN], bel[MAXN], tot, scc, ins[MAXN], sta[MAXN], top; 
int W[MAXN], V[MAXN], indeg[MAXN], dp[MAXN][MAXN];
struct edge {
    int v;
    edge *next;
}pool[MAXN * 2], *head[MAXN];
inline void addedge(int u, int v) {
    edge *p = &pool[++cnt];
    p->v = v, p->next = head[u], head[u] = p; 
}
void tarjan(int u) {
    dfn[u] = low[u] = ++tot; sta[++top] = u; ins[u] = 1;
    for(edge *p = head[u]; p; p = p->next) {
        int v = p->v;
        if(!dfn[v]) {
            tarjan(v); 
            low[u] = min(low[u], low[v]);
        } else if(ins[v]) 
            low[u] = min(low[u], dfn[v]);
    }
    if(dfn[u] == low[u]) {
        ++scc;
        while(sta[top + 1] != u) {
            bel[sta[top]] = scc;
            W[scc] += w[sta[top]]; 
            V[scc] += a[sta[top]];
            ins[sta[top--]] = 0;
        }
    }
}
void solve(int u) {
    for(int i = W[u]; i <= m; i++)
        dp[u][i] = V[u];
    for(edge *p = head[u]; p; p = p->next) {
        int v = p->v;
        solve(v); int k = m - W[u];
        for(int i = k; i >= 0; i--) 
            for(int j = 0; j <= i; j++)
                dp[u][i + W[u]] = 
                max(dp[u][i + W[u]], 
                dp[v][j] + dp[u][i + W[u] - j]);
    }
}
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", &a[i]);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &d[i]); if(d[i]) addedge(d[i], i);
    }
    for(int i = 1; i <= n; i++)    
        if(!dfn[i]) tarjan(i);
    for(int i = 0; i <= n; i++) head[i] = NULL; cnt = 0;
    for(int i = 1; i <= n; i++)
        if(bel[d[i]] != bel[i]) {
            addedge(bel[d[i]], bel[i]);
            indeg[bel[i]]++;
        }
    for(int i = 1; i <= scc; i++) 
        if(!indeg[i]) addedge(0, i);
    solve(0);
    printf("%d\n", dp[0][m]);
    return 0;
}

评论

  • steven张
    %%%
  • 灯火丿葳蕤
    为什么是倒序和顺序,大佬能解释一下吗
  • 灯火丿葳蕤
    哦,明白了
  • duyi
    所以这应该是一个基环外向树森林QwQ
作者: xyz32768 更新时间: 2017-08-07 18:46  在Ta的博客查看 举报    5  

强连通分量+树形$DP$。

首先对于每个$i$,从$i$向$Di$建一条有向边。

在这里我们发现,依赖关系可以形成环。对于一个环,里面的节点要么都选,要么都不选。

所以,这里先$Tarjan$强连通分量缩点,构成一个新图,这样新图里的每个节点可以看成一个整体考虑(因为对应的原图里的节点要么都选要么都不选)。然后新建一个虚拟节点,向新图里所有的入度为$0$的节点建一条有向边,构成一棵树,以虚拟节点作为根。

建树完毕后,在构成的树上做$DP$。

以下$cost[i]$和$val[i]$分别为树上每个节点的费用和价值,设$f[u][i]$为在节点$u$的子树内,费用限制为$i$的条件下能取到的最大价值,此时对于每个$u$,首先把$f[u][i]$($cost[u]<=i<=m$)设为$val[u]$。

然后如果第一层循环$u$的子节点$v$,第二层倒序循环$i$(从$m-cost[u]$到$0$),第三层顺序循环节点$v$的子树的费用限制$j$(从$0$到$i$),则转移方程为:$f[u][i+cost[u]]=max(f[u][i+cost[u]],f[u][i+cost[u]-j]+f[v][j])$。

最后答案为$f[虚拟节点][m]$。

代码:

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
inline int read() {
    int res = 0; bool bo = 0; char c;
    while (((c = getchar()) < '0' || c > '9') && c != '-');
    if (c == '-') bo = 1; else res = c - 48;
    while ((c = getchar()) >= '0' && c <= '9')
        res = (res << 3) + (res << 1) + (c - 48);
    return bo ? ~res + 1 : res;
}
const int N = 105, M = 505;
int n, m, W[N], V[N], f[N][M], ecnt, nxt[M], adj[N], go[M], top,
sta[N], dfn[N], low[N], times, num, bel[N], cost[N], val[N], ecnt2,
nxt2[M], adj2[N], go2[M], d[N];
bool ins[N], G[N][N];
void add_edge(int u, int v) {
    nxt[++ecnt] = adj[u]; adj[u] = ecnt; go[ecnt] = v;
}
void add_edge2(int u, int v) {
    nxt2[++ecnt2] = adj2[u]; adj2[u] = ecnt2; go2[ecnt2] = v;
}
void Tarjan(int u) {
    dfn[u] = low[u] = ++times;
    sta[++top] = u; ins[u] = 1;
    for (int e = adj[u], v; e; e = nxt[e])
        if (!dfn[v = go[e]]) {
            Tarjan(v);
            low[u] = min(low[u], low[v]);
        }
        else if (ins[v]) low[u] = min(low[u], dfn[v]);
    if (dfn[u] == low[u]) {
        int v; bel[u] = ++num; ins[u] = 0;
        while (v = sta[top--], v != u) bel[v] = num, ins[v] = 0;
    }
}
void dp(int u) {
    int i, j;
    for (i = cost[u]; i <= m; i++) f[u][i] = val[u];
    for (int e = adj2[u], v; e; e = nxt2[e]) {
        dp(v = go2[e]);
        for (i = m - cost[u]; i >= 0; i--) for (j = 0; j <= i; j++)
            f[u][i + cost[u]] = max(f[u][i + cost[u]],
                f[u][i + cost[u] - j] + f[v][j]);
    }
}
int main() {
    int i, j, x; n = read(); m = read();
    for (i = 1; i <= n; i++) W[i] = read();
    for (i = 1; i <= n; i++) V[i] = read();
    for (i = 1; i <= n; i++) if (x = read()) add_edge(x, i);
    for (i = 1; i <= n; i++) if (!dfn[i]) Tarjan(i);
    for (i = 1; i <= n; i++) {
        cost[bel[i]] += W[i]; val[bel[i]] += V[i];
        for (int e = adj[i]; e; e = nxt[e])
            if (bel[i] != bel[go[e]]) G[bel[i]][bel[go[e]]] = 1,
                d[bel[go[e]]]++;
    }
    for (i = 1; i <= num; i++) for (j = 1; j <= num; j++)
        if (G[i][j]) add_edge2(i, j);
    for (i = 1; i <= num; i++) if (!d[i])
        add_edge2(num + 1, i);
    printf("%d\n", (dp(num + 1), f[num + 1][m]));
    return 0;
}

评论

  • kai586123
    低复杂度的必须顶%%%
作者: lzoilxy 更新时间: 2018-12-31 13:36  在Ta的博客查看 举报    4  

来一篇O(nm)的题解。

其实前面没有什么区别,我们先按照依赖关系连边,然后把相互依赖的一些软件缩点。

缩完点后,再建一遍图,注意第二次建图要用缩完点后的编号,第二次建出来的图肯定是棵树,那么我们就可以先跑一遍dfs,处理出每个节点的dfs序,在dfs序上DP。

i表示dfs序,dfn表示dfs序为i的节点,sum[i]表示i节点的占用空间,val[i]表示选i节点的价值

选当前节点:dp[i+1][j+sum[dfn[i]]=max(dp[i][j]+val[dfn[i]])

不选当前节点:dp[i+siz[dfn[i]][j]=max(dp[i][j]);

因为我们要保证选这个节点的时候它依赖的节点(包括直接和间接依赖)都选了我们要记录它所有祖先的sum的和。

#include<algorithm>
#include<cstdio>
#define mxn 110
using namespace std;
int n,m,K,sl,ans,w[mxn],s[mxn],d[mxn],siz[mxn],pre[mxn],sum[mxn],val[mxn],dp[mxn][510];
int tim,top,id[mxn],stk[mxn],vis[mxn],dfn[mxn],low[mxn];
int t,h[mxn];
struct edge
{
    int fr,to,nxt;
}e[mxn];
inline char gc()
{
    static char buf[1<<16],*S,*T;
    if(S==T){T=(S=buf)+fread(buf,1,1<<16,stdin);if(S==T)return EOF;}
    return *S++;
}
inline int rd()
{
    sl=0;
    char ch=gc();
    while(ch<'0'||'9'<ch) ch=gc();
    while('0'<=ch&&ch<='9') sl=sl*10+ch-'0',ch=gc();
    return sl;
}
inline void add(int u,int v) {e[++t]=(edge){u,v,h[u]};h[u]=t;}
void tarjan(int u)
{
    dfn[u]=low[u]=++tim;
    stk[++top]=u;
    vis[u]=1;
    int v;
    for(int i=h[u];i;i=e[i].nxt)
        if(!dfn[v=e[i].to])
            tarjan(v),low[u]=min(low[u],low[v]);
        else if(vis[v]) low[u]=min(low[u],dfn[v]);
    if(dfn[u]==low[u])
    {
        ++K;
        do
        {
            v=stk[top--];
            sum[K]+=w[v];
            val[K]+=s[v];
            vis[v]=0;
            id[v]=K;
        }while(u!=v);
    }
}
void dfs(int u)
{
    int v;dfn[++tim]=u;siz[u]=1;
    for(int i=h[u];i;i=e[i].nxt)
        pre[v=e[i].to]=pre[u]+sum[u],
        dfs(v),siz[u]+=siz[v];
}
inline void upd(int &x,int y) {if(y>x) x=y;}
int main()
{
    n=rd();m=rd();int x;
    for(int i=1;i<=n;++i) w[i]=rd();
    for(int i=1;i<=n;++i) s[i]=rd();
    for(int i=1;i<=n;++i)
    {
        x=rd();
        if(x) add(x,i);
    }
    for(int i=1;i<=n;++i)
        if(!dfn[i])
            tarjan(i);
    top=t;t=0;fill(h+1,h+K+1,0);
    for(int i=1;i<=top;++i)
        if(id[e[i].fr]!=id[e[i].to])
            d[id[e[i].to]]++,add(id[e[i].fr],id[e[i].to]);
    for(int i=1;i<=K;++i)
        if(!d[i])
            add(0,i);
    tim=0;dfs(0);
    for(int i=1;i<=tim;++i)
    {
        for(int j=pre[dfn[i]];j<=m-sum[dfn[i]];++j)
            upd(dp[i+1][j+sum[dfn[i]]],dp[i][j]+val[dfn[i]]);
        for(int j=pre[dfn[i]];j<=m;++j)
            upd(dp[i+siz[dfn[i]]][j],dp[i][j]);
    }
    printf("%d\n",dp[tim+1][m]);
    return 0;
}

评论

  • KajKeusaka
    哈哈哈玩蛇皮
  • 可口可乐头
    (我也忘了)
作者: Eziotao 更新时间: 2018-07-03 20:39  在Ta的博客查看 举报    4  

考试爆炸很绝望.jpg

别告诉我只有我忘了缩点

每个软件只直接依赖另一个(不依赖的就假设依赖0嘛)。画图,三分钟后。
树上的背包问题嘛,好说。对于每个节点,选了它才能选它的子节点,那我们设f[i][j]表示到i号点了,用j这样大的空间能得到的最大价值。设d是i的子节点,那么f[d][j]可以从f[i][j-w[d]-w[i]]+v[i]得到(为什么要减w[i],加v[i]?因为你必须选了它的父亲节点,才能选到它,对吧),那么我找出每个子树用一定数量的空间能到的最大价值,分别枚举每种情况(d1用多少,d2用多少...),统一在i里,统计一下,答案好像就出来了(如果不是很懂,在下自以为注释写得还行,,)。然后我愉快的打完了板子(好像还出锅了?),继续往后做。
这时看起来似乎没什么不对。
直到考完后,大仙(fyj)问我:“你tarjan怎么打的?”我:一脸懵逼。看看题目,没有说不能成环啊,如果成环,要么都不选,要么都选,是吧。于是我愉快的RE了。再看看题,如果成环,那么这个环一定不依赖任何点(仿佛说了句废话,每个点只能依赖最多一个,依赖成环了环里哪来的空的点依赖别的),继续想,变成一个森林了。树根不依赖怎么办呢?反正0无贡献无占位,那就把树根都置为连到0好了。然后,就可以愉快的再打一个板子了(tarjan)。
//果断树形dp,结果忘了一个很重要的东西,, 
#include<bits/stdc++.h>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<deque>
#include<iostream>
#define ll long long 
#define re register
#define inf 0x7f7f7f7f
#define inl inline
#define debug printf("debug\n");
//#define eps 1e-8
//#pragma comment(linker, "/STACK:1024000000,1024000000")
//#pragma GCC optimize (2)
//#pragma G++ optimize (2)
using namespace std;
//const ll mod;(同学看到头文件风格就知道是我2333 )
inl ll read() {
    re ll x = 0; re int f = 1;
    char ch = getchar();
    while(ch<'0'||ch>'9') { if(ch== '-' ) f = -1; ch = getchar(); }
    while(ch>='0'&&ch<='9') {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return x * f;
}
inl void write(ll x){
    if(x>=10)write(x/10);
    putchar(x%10+'0');
}
inl void writeln(ll x){
    if(x<0) {x=-x;putchar('-');}
    write(x); puts("");
}
inl void FR(){
    freopen("software.in","r",stdin);
    freopen("software.out","w",stdout);
} 
inl void FC(){
    fclose(stdin);
    fclose(stdout);
}//考试题,, 
ll cnt,head[105];
struct Node{
    ll u,v,nxt;
}e[105<<1],en[105<<1];//有可能循环依赖,必须缩点
ll w[105],v[105],n,m;//en是重建的图 ,w,v原权值和原花费 
void adde(ll u,ll v){
    e[++cnt].u=u;e[cnt].v=v;
    e[cnt].nxt=head[u];
    head[u]=cnt;
}
ll head2[105];
void adden(ll u,ll v){
    en[++cnt].u=u;en[cnt].v=v;
    en[cnt].nxt=head2[u];
    head2[u]=cnt;
} 
ll d[105];//dfsn
ll f[105][505];//一维处理到几号店,第二维花费多少 
ll ssw[105],ssv[105];//缩点后每个点的花费和权值 
ll tot=0;
void dfs(ll x){
    d[++tot]=x;
    if(!head2[x]){
        for(re ll i=ssw[x];i<=m;i++){
            f[x][i]=ssv[x];
        }
        return ;
    }//没有子节点,自己返回美滋滋 
    for(re ll i=head2[x];i;i=en[i].nxt) dfs(en[i].v);//有子节点先看子节点 
    for(re ll i=head2[x];i;i=en[i].nxt){
        re ll y=en[i].v;//枚举子节点 
        for(re ll tow=m;tow>=0;tow--){//在这个子节点分配的 
            for(re ll j=0;j<=tow;j++){//剩余的(分配到其他子节点的,自己的在后面加) 
                f[x][tow]=max(f[x][tow],f[x][tow-j]+f[y][j]);//大仙我不是故意打出fyj的!! 
            }
        }
    }
    for(re ll i=m;i>=0;i--){
        if(i>=ssw[x]) f[x][i]=f[x][i-ssw[x]]+ssv[x];//可以选 
        else f[x][i]=0;// 不能选,玩蛇皮 
    }
}
vector<ll>S[105];//tarjan用 
ll low[105],dfn[105],cmt,pre[105],bel[105];//好像不需要开这么多(管他呢反正不卡空间 ) 
ll in[105];//(tarjan:在不在栈里   重置后:有无依赖) 
stack<ll>Q;//tarjan大法好,,, 
void dfs1(ll x){
    dfn[x]=++tot;low[x]=tot;pre[tot]=x;Q.push(x);
    in[x]=1;
    for(re ll i=head[x];i;i=e[i].nxt){
        re ll sv=e[i].v;
        if(!dfn[sv]) {
            dfs1(sv);
            low[x]=min(low[x],low[sv]);
        }
        else if(in[sv]){
            low[x]=low[sv];
        }
    }
    if(low[x]==dfn[x]){
        ++cmt;
        ll ssx;
        do{
            ssx=Q.top();
            S[cmt].push_back(ssx);
            bel[ssx]=cmt;
            in[ssx]=0;
            Q.pop();
        }while(ssx!=x);
    }
}//tarjan自觉套模板(太久没看打到泪奔) 

inl void tarjan(){
    for(re ll i=1;i<=n;i++){
        if(!dfn[i]) dfs1(i);
    }
}//写出来感觉好看一点, 
int main(){
//  FR(); 
    n=read(),m=read();
    for(re ll i=1;i<=n;i++) w[i]=read();
    for(re ll i=1;i<=n;i++) v[i]=read();
    w[0]=0;v[0]=0;//0号点无花费(也无贡献,,) 
    for(re ll i=1;i<=n;i++){
        ll x=read();adde(x,i);
    }//加边,, 
    tarjan();//缩点 
    memset(in,0,sizeof(in));//缩完了,忙完了这阵子,in就可以忙下阵子了 
    cnt=0;
    for(re ll i=1;i<=n;i++) {
        for(re ll j=head[i];j;j=e[j].nxt){
            re ll x=e[j].u,y=e[j].v;
            if(bel[x]==bel[y]) continue ;
            adden(bel[x],bel[y]);
            in[bel[y]]++;
        }//重构图,貌似没什么问题吧,,(出锅了请联系fyj,他教我的!) 
    }
    for(re ll i=1;i<=cmt;i++){
        if(!in[i]) adden(0,i);//把没有依 赖的设为依赖0,就可以一次树形跑完了 
        for(re ll j=0;j<S[i].size();j++){
            ssw[i]+=w[S[i][j]];
            ssv[i]+=v[S[i][j]];
        }//缩点后各点权值及花费 
    }
    tot=0;
    dfs(0);//dp一波 
    writeln(f[0][m]);//输出 
//  FC();
    return 0;
}
 
反馈
如果你认为某个题解有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。