YBTOJ 软件安装

题面：​​洛谷传送门​​

题目算法要素:tarjan+树形dp

题目分析：

一、总体概括

可以发现一个环中的点必须同时被选择，因此很容易能想到要tarjan缩点。

缩点后形成一张DAG，由于题目的条件，d[i]=0表示一个软件没有另一个软件为前提，因此有一个超级源点0。可以考虑从0点开始，跑一遍树形dp（树上背包），即可得出答案。

二（细节一）：为什么不能用拓扑dp求解：

如果跑一遍拓扑dp，可以得出以每一个点为终点的最大权链，但是各个链中显然有重合的可能性，因此无法直接通过再跑一遍01背包的方式将以每个点为终点的最大权链合成整张DAG的最优解。

因此拓扑dp显然不行。

这道题也告诉我们缩点不是一定要用拓扑dp求解的。

三（细节二）：如何在树形dp中强制选择当前点

我们使用dp式：f[u][j]表示在以u根的子树中，耗费j的存储空间，能得到的软件的最大总价值。

但是别忘了只有选择了根节点，才能选择子树中的点。

因此我们加上一条限制条件：对于f[u][j]，强制要求选择点u。

这其实是一类问题：如何在树形dp中强制选择一棵子树的根节点

肯定要考虑枚举j和子树费用k的过程（修改转移式）

如果没有这个条件，我们显然会把状态转移写成这个样子

令u的一个子节点为v
for(int j=sumw[u];j<=m;++j) f[u][j]=sumv[u]; 
for(int j=m;j>=0;--j)
{
  for(int k=0;k<=j;++k)
    f[u][j]=max(f[u][j],f[u][j-k]+f[v][k]);
}
      

加上这个限制条件，就相当于：给选择根节点留下足够的存储空间

for(int j=sumw[u];j<=m;++j) f[u][j]=sumv[u]; 
for(int j=m-sumw[u];j>=0;--j)
{
  for(int k=0;k<=j;++k)
    f[u][j+sumw[u]]=max(f[u][j+sumw[u]],f[u][j+sumw[u]-k]+f[v][k]);
}
      

由于每一个位置都一定给u留够了空间，且每次计算空间都加上sumw[u]，另外，最开始的初始化是给每个未选择的空间都赋上了sumv[u],因此sumv[u]一定会被选择。

或者还有一种写法：

就是在子树不包括u的部分选择的空间一定比在子树包括u的部分选择的空间少一个sumw[u]，也就是一定把u选择上了。

void dp(int now)
{
  for(int i=sumw[now];i<=m;++i) f[now][i]=sumv[now];
  for(int i=head2[now];~i;i=e2[i].nxt)
  {
    int v=e2[i].v;
    dp(v);
    for(int j=m;j>=sumw[now];--j)
    {
      for(int k=0;k<=j-sumw[now];++k)
      {
        f[now][j]=max(f[now][j],f[now][j-k]+f[v][k]);
      }
    }
  }
}
      

Code

#include<bits/stdc++.h>
using namespace std;
const int maxn=550;
int n,m,w[maxn],v[maxn],d[maxn],tot,col[maxn];
int dfn[maxn],low[maxn],Time,sumw[maxn],sumv[maxn];
int ecnt=-1,ecnt2=-1,head[maxn],head2[maxn];
int s[maxn],top,indu[maxn],f[105][505];
struct mint
{
  int nxt,u,v;  
}e[maxn],e2[maxn];
inline void addline(int u,int v)
{
  e[++ecnt].nxt=head[u];
  e[ecnt].u=u;
  e[ecnt].v=v;
  head[u]=ecnt;
}
inline void addline2(int u,int v)
{
  e2[++ecnt2].nxt=head2[u];
  e2[ecnt2].u=u;
  e2[ecnt2].v=v;
  head2[u]=ecnt2; 
}
void tarjan(int now)
{
  dfn[now]=low[now]=++Time;
  s[++top]=now;
  for(int i=head[now];~i;i=e[i].nxt)
  {
    int v=e[i].v;
    if(!dfn[v])
    {
      tarjan(v);
      low[now]=min(low[now],low[v]);  
    }
    else if(!col[v]) low[now]=min(low[now],dfn[v]);
  }
  if(dfn[now]==low[now])
  {
    tot++;
    int cur;
    do
    {
      cur=s[top--];
      col[cur]=tot;
      sumw[tot]+=w[cur];
      sumv[tot]+=v[cur];
    }
    while(cur!=now);
  }
}
void dp(int now)
{
  for(int i=sumw[now];i<=m;++i) f[now][i]=sumv[now];
  for(int i=head2[now];~i;i=e2[i].nxt)
  {
    int v=e2[i].v;
    dp(v);
    for(int j=m-sumw[now];j>=0;--j)
    {
      for(int k=0;k<=j;++k)
      {
        f[now][j+sumw[now]]=max(f[now][j+sumw[now]],f[now][j+sumw[now]-k]+f[v][k]);
      }
    }
  }
}
int main()
{
  scanf("%d%d",&n,&m);
  memset(head,-1,sizeof(head));
  memset(head2,-1,sizeof(head2));
  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]);
    addline(d[i],i);
  }
  for(int i=1;i<=n;++i) if(!dfn[i]) tarjan(i);
  for(int i=0;i<m;++i)
  {
    if(col[e[i].v] != col[e[i].u])
    {
      addline2(col[e[i].u],col[e[i].v]); 
      indu[col[e[i].v]]++;
    }
  }
  for(int i=1;i<=tot;++i) if(!indu[i]) addline2(0,i);
  dp(0);
  printf("%d",f[0][m]);
  return 0; 
}