luogu P2515 [HAOI2010]软件安装

看到唯一的依赖关系,容易想到树型dp,即\(f_{i,j}\)表示选点\(i\)及子树内连通的点,代价为\(j\)的最大价值,然后就是选课那道题

但是要注意

1.题目中的依赖关系不一定是树,可能会有环,我们可以发现环里面的点要么全选要么全不选,要用tarjan把环缩为一个点,同时把代价和价值加到缩后的点上

2.记得把缩完点后所有没有依赖关系的点连到超级点(0点上)

3.树型dp别写错了,注意边界

强行连踩三雷qwq

// luogu-judger-enable-o2

#include<bits/stdc++.h>

#define LL long long

#define il inline

#define re register

#define inf 2099999999

#define max(a,b) ((a)>(b)?(a):(b))

#define min(a,b) ((a)<(b)?(a):(b))

#define S(a) (1<<(a-1))

using namespace std;

const int N=100+10,M=500+10;

il LL rd()

{

    re LL x=0,w=1;re char ch=0;

    while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}

    while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}

    return x*w;

}

int to[N<<1],nt[N<<1],hd[N],tot=1;

il void add(int x,int y)

{

  ++tot,to[tot]=y,nt[tot]=hd[x],hd[x]=tot;

}

int n,m,a[N][2],d[N],f[N][M];

int dfn[N],low[N],po[N],st[N],tt,ti;

char ista[N],cq[N];

il void tj(int x)

{

  dfn[x]=low[x]=++ti,st[++tt]=x,ista[x]=1;

  for(int i=hd[x];i;i=nt[i])

    {

      int y=to[i];

      if(!dfn[y]) tj(y),low[x]=min(low[x],low[y]);

      else if(ista[y]) low[x]=min(low[x],low[y]);

    }

  if(low[x]==dfn[x])

    {

      while(tt)

        {

          int y=st[tt--];

          ista[y]=0,po[y]=x;

          if(x==y) break;

          a[x][0]+=a[y][0],a[x][1]+=a[y][1],cq[x]=1;

        }

    }

}

il void dp(int x)

{

  //if(a[x][0]>m) return;

  f[x][a[x][0]]=a[x][1];

  for(int j=0;j<a[x][0];j++) f[x][j]=0;

  for(int i=hd[x];i;i=nt[i])

    {

      int y=to[i];

      dp(y);

      for(int k=m;k>=a[x][0];k--)

      for(int j=a[y][0];k-j>=a[x][0];j++)

        f[x][k]=max(f[x][k],f[x][k-j]+f[y][j]);

    }

}

int main()

{

  n=rd(),m=rd();

  for(int i=1;i<=n;i++) a[i][0]=rd();

  for(int i=1;i<=n;i++) a[i][1]=rd();

  for(int i=1;i<=n;i++) d[i]=rd(),add(d[i],i),po[i]=i;

  for(int i=0;i<=n;i++)

    if(!dfn[i]) tj(i);

  memset(hd,0,sizeof(hd)),tot=1;

  for(int i=1;i<=n;i++)

    if(po[i]!=po[d[i]]) add(po[d[i]],po[i]);

  for(int i=1;i<=n;i++)

    if(cq[i]&&po[i]==i) add(0,i);

  memset(f,-0x3f3f3f,sizeof(f));

  dp(0);

  int ans=0;

  for(int i=0;i<=m;i++) ans=max(ans,f[0][i]);

  printf("%d\n",ans);

  return 0;

}

巴特西

luogu P2515 [HAOI2010]软件安装

最新文章

热门文章