[ Luogu 1273 ] 有线电视网

\(\\\)

\(Description\)

一棵\(N\)个节点的树，编号在\([N-M+1,N]\)内的点必定为叶子节点，且这些点都有一个收益值\(Val_i\)，同时每一条树边都有一个代价。

访问叶节点必须从\(1\)号点出发，经过所有必须的树边到达，每条树边的代价只计算一次。

求在总收益\(-\)总代价不为负的前提下，最多能到达多少个节点。

\(N,K\in [1,3\times10^3]\)

\(\\\)

\(Solution\)

树形背包。设\(f[i][j]\)表示当前在\(i\)号节点，覆盖其子树内的\(j\)个节点的最大利润。

在背包的时候注意维护的\(size_i\)不再是子树大小，而是子树内有多少个编号在\([N-M+1,N]\)范围内的点。

转移为\(f[u][j]=max(f[u][j],f[u][j-k]+f[v][k]-e[i].w)\ \big|\ j\in[0,size_u],k\in[0,size_v]\)。

初始化\(f[i][0]=0,f[i][j|j\not=0]=-inf\)。边界为\(f\bigg[i\ \big|\ i\in [N-M+1,N]\bigg]\bigg[1\bigg]=Val_i\)。

然后答案就是最大的\(i\)满足\(f[1][i]\ge 0\)。

\(\\\)

\(Code\)

#include<cmath>

#include<cstdio>

#include<cctype>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

#define N 3010

#define R register

#define gc getchar

using namespace std;

inline int rd(){

  int x=0; bool f=0; char c=gc();

  while(!isdigit(c)){if(c=='-')f=1;c=gc();}

  while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc();}

  return f?-x:x;

}

int n,m,tot,sz[N],hd[N],val[N],f[N][N];

struct edge{int w,to,nxt;}e[N];

inline void add(int u,int v,int w){

  e[++tot].to=v; e[tot].w=w;

  e[tot].nxt=hd[u]; hd[u]=tot;

}

void dfs(int u,int fa){

  if(u>n-m){sz[u]=1;return;}

  for(R int i=hd[u],v;i;i=e[i].nxt)

    if((v=e[i].to)!=fa){

      dfs(v,u); sz[u]+=sz[v];

      for(R int j=sz[u];j;--j)

        for(R int k=sz[v];k;--k)

          f[u][j]=max(f[u][j],f[u][j-k]+f[v][k]-e[i].w);

    }

}

int main(){

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

  for(R int i=1,x;i<=n-m;++i){

    x=rd();

    for(R int j=1,v,w;j<=x;++j){v=rd();w=rd();add(i,v,w);}

  }

  for(R int i=1;i<=m;++i) val[i]=rd();

  memset(f,0xcf,sizeof(f));

  for(R int i=1;i<=n;++i) f[i][0]=0;

  for(R int i=1;i<=m;++i) f[i+n-m][1]=val[i];

  dfs(1,0);

  for(R int i=m;i;--i)

    if(f[1][i]>=0){printf("%d",i);return 0;}

  return 0;

}

巴特西

[ Luogu 1273 ] 有线电视网

\(Description\)

\(Solution\)

\(Code\)

最新文章

热门文章