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