P2515 [HAOI2010]软件安装 题解


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

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

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

评论

  • Simpson561
    错别字……
  • 杨铠远
    建议置顶!!!
  • huayucaiji
    ju
  • hhxxttxs_WHY
    讲得很好,谢谢 %%%%%%
作者: 凤睚 更新时间: 2017-10-26 15:58  在Ta的博客查看 举报    26  

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

见图的时候是从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]);
}

评论

  • kai586123
    低复杂度的必须顶%%%
  • SSL_XJQ_逐风之刃
    送你上去
  • AK新手村
    终于有dfs序的树形背包了,必须顶
  • yuzhechuan
    这刷表背包+左闭右开区间(?)写得太巧妙了!
作者: lzoilxy 更新时间: 2018-12-31 13:36  在Ta的博客查看 举报    18  

来一篇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;
}

评论

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

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;
}

评论

  • 浅爱
    你是神经病吗?int写那么长搞锤子,看到特别不爽
作者: KevinYu 更新时间: 2018-11-28 21:12  在Ta的博客查看 举报    4  

这一题真是无限次苦苦挣扎得出的产物啊。
我们来一步步地分析题面:
1.这一道题乍一看像是一个树上背包的问题,我们于是得出程序的主要框架:树形dp。
我们先建图,用up[i]来存储i的先决条件(注意:x,i不要搞反了)。

for(int i=1;i<=n;i++)
    {
        int x;
        scanf("%d",&x);
        up[i]=x;
        if(x!=0)addedge(x,i);
    }

但是,题目描述中并没有说这个东西一定是一棵树,它有可能是一张带环图,也可能是一个森林。
例如,考虑这样的一个依赖关系:

4 9
3 3 3 1 
2 3 4 6
2 3 1 1

我们发现:这个图建完后是一个带环图。1,2,3号节点互为依赖条件。一旦有其中任何一个点没有被选择,整个环里面的所有内容都无法被使用。
我们重新观察这张图,我们发现1,2,3号节点的共性:我们可以对它整个选择,也可以对它整个不选择,对其中的任何一个真子集都没有意义。
对于环中点有共性的图,我们考虑用缩点来解决问题(本题中以tarjan算法为例)。
2.缩点过程(会tarjan的可以跳过):
tarjan算法基于时间戳与dfs实现,我们将一个点被发现的时间存入dfn数组中,然后将一个点够追溯到的最早的栈中节点的次序计入low数组中。
我们来过一遍算法流程: 1.初始化:

void tarjan(int u)
{
    low[u]=dfn[u]=++now;
    hep[++top]=u;vis[u]=1;

我们可以发现,tarjan的初始化中要完成2个工作:
①.更新时间戳与low数组
②.将节点压栈并打上标记
2.tarjan主过程:

    for(int i=head[u];i!=-1;i=a[i].next)
    {
        int v=a[i].to;
        if(!dfn[v]){tarjan(v);low[u]=min(low[u],low[v]);}
            else if(vis[v])low[u]=min(low[u],dfn[v]);
    }

我们来慢慢分析它:
我们首先遍历每一条边,然后对能到达的点进行访问:

    for(int i=head[u];i!=-1;i=a[i].next)
    {
        int v=a[i].to;

我们需要分出三种v点:
1.从没访问过的
对于这个点,我们将它作为下一个点,递归地进行tarjan过程。
在tarjan结束后,更新它的low数组。
你可以把更新的过程理解成从tarjan过程里回传来了它的low值,我们将它的low值与现在这个节点的low值比较,并取较小值。

        if(!dfn[v])
        {
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }

2.访问过,并在栈里的
这种节点是可以到达当前节点的,我们发现了这样一个点,就是发现了一个强连通分量,于是我们对当前点的low值进行更新

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

3.访问过,但不在栈里的
都不能到达你,跟你有什么关系吗,直接忽视掉就行了。
3.退栈:

    if(dfn[u]==low[u])
    {
        ++tot;
        vis[u]=0;
        while(hep[top+1]!=u)
        {
            fa[hep[top]]=tot;
            vis[hep[top--]]=0;
        }
    }
}

整个退栈过程就是记录强连通分量的过程,下面我就来详细解释一下。
退栈的条件是dfn[u]==low[u],代表着我们的遍历过程已经触底,并且回溯回来了。
在我们当前点上方的都是什么点呢?都是在同一个强连通分量中的点。所以我们将其全部取出,并记录进一个强连通分量中(一般管这个叫“染色”)。
tarjan缩点过程完整代码:

void tarjan(int u)
{
    low[u]=dfn[u]=++now;
    hep[++top]=u;vis[u]=1;
    for(int i=head[u];i!=-1;i=a[i].next)
    {
        int v=a[i].to;
        if(!dfn[v])
        {
            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])
    {
        ++tot;
        vis[u]=0;
        while(hep[top+1]!=u)
        {
            fa[hep[top]]=tot;
            vis[hep[top--]]=0;
        }
    }
}

3.重新建图:
我们通过缩点,将这个图变成一个有向无环图(树或森林),我们需要重新建一个图(注意起点和终点的顺序):

    for(int i=1;i<=n;i++)
    {
        val[fa[i]]+=v[i];cost[fa[i]]+=w[i];
        if(fa[i]!=fa[up[i]]&&up[i]!=0)
        {
            addag(fa[up[i]],fa[i]);
            usd[fa[i]]++;
        }
    }

我们为了将其转换成一棵树,将这个图每一个根节点都连到一个点上:

    int s=tot+1;
    for(int i=1;i<=tot;i++)if(!usd[i])addag(s,i);
    cost[s]=0;val[s]=0;

4.树形dp:
我们用dfs来描述dp过程
规定dfs(u)表示进行到了当前节点,f[i][j]代表当前节点是i,还剩j的空间。
算法流程如下:
1.初始化

    for(int i=cost[u];i<=m;i++)f[u][i]=val[u];

我们将每一个大于当前点花费的f数组初始化为u的价值。
2.遍历每一条边:

    for(int i=hag[u];i!=-1;i=dag[i].next)
    {
        int v=dag[i].to;

3.根据转移方程完成算法:
我们取了下一个点,并意识到:我们可以选当前点,也可以不选当前点,若不选当前点,其所有子节点都无法被选择。 依此我们得到状态转移方程:

f[u][j+cost[u]]={max(f[u][j+cost[u]],f[u][j+cost[u]-q]+f[v][q]);}

就是取子节点中的最优解,并加上当前节点的权值。

        dfs(v);
        for(int j=m-cost[u];j>=0;j--)
        {
            for(int q=0;q<=j;q++)
            {
                f[u][j+cost[u]]=max(f[u][j+cost[u]],f[u][j+cost[u]-q]+f[v][q]);
            }
        }
    }
}

dfs过程就此结束。
完整代码:

#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<climits>
#include<ctime>
#include<algorithm>
#include<complex>
#include<iostream>
#include<map>
#include<queue>
#include<vector>
#define INF 0x3f3f3f3f
#define ll long long
using namespace std;
struct edge
{
    int to,next;
}a[1010],dag[1010];
int hag[1010];
int head[1010];
int v[1010];
int w[1010];
int cost[1010];
int val[1010];
int f[1010][5050];
int low[1010];
int dfn[1010];
int now(0);
int hep[1010];
int top(0);
int vis[1010];
int fa[1010];
int up[1010];
int usd[1010];
int cnt(0);
int cal(0);
int tot(0);
int n,m;
void addedge(int xi,int yi)
{
    a[cnt].to=yi;
    a[cnt].next=head[xi];
    head[xi]=cnt++;
}
void addag(int xi,int yi)
{
    dag[cal].to=yi;
    dag[cal].next=hag[xi];
    hag[xi]=cal++;
}
void tarjan(int u)
{
    low[u]=dfn[u]=++now;
    hep[++top]=u;vis[u]=1;
    for(int i=head[u];i!=-1;i=a[i].next)
    {
        int v=a[i].to;
        if(!dfn[v])
        {
            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])
    {
        ++tot;
        vis[u]=0;
        while(hep[top+1]!=u)
        {
            fa[hep[top]]=tot;
            vis[hep[top--]]=0;
        }
    }
}
void dfs(int u)
{
    for(int i=cost[u];i<=m;i++)f[u][i]=val[u];
    for(int i=hag[u];i!=-1;i=dag[i].next)
    {
        int v=dag[i].to;
        dfs(v);
        for(int j=m-cost[u];j>=0;j--)
        {
            for(int q=0;q<=j;q++)
            {
                f[u][j+cost[u]]=max(f[u][j+cost[u]],f[u][j+cost[u]-q]+f[v][q]);
            }
        }
    }
}
int main()
{
    memset(head,-1,sizeof(head));
    memset(hag,-1,sizeof(hag));
    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++)
    {
        int x;
        scanf("%d",&x);
        up[i]=x;
        if(x!=0)addedge(x,i);
    }
    for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i);
    for(int i=1;i<=n;i++)
    {
        val[fa[i]]+=v[i];cost[fa[i]]+=w[i];
        if(fa[i]!=fa[up[i]]&&up[i]!=0)
        {
            addag(fa[up[i]],fa[i]);
            usd[fa[i]]++;
        }
    }
    int s=tot+1;
    for(int i=1;i<=tot;i++)if(!usd[i])addag(s,i);
    cost[s]=0;val[s]=0;
    dfs(s);
    printf("%d",f[s][m+cost[s]]);
    return 0;
}
 
反馈
如果你认为某个题解有问题,欢迎向洛谷反馈,以帮助更多的同学。



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