P1273 有线电视网(树形dp)

P1273 有线电视网

• 显然树形dp，用f[i][j]表示对于节点i选择它的j个儿子所得的最大收益
• 最后答案即为使f[1][i]非负的最大的i
• 代码：

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 using namespace std;

 #define N (3000+100)

 #define res register int

 inline int read()

 {

     int x(),f(); char ch;

     while(!isdigit(ch=getchar())) if(ch=='-') f=-;

     while(isdigit(ch)) x=x*+ch-'',ch=getchar();

     return f*x;

 }

 int head[N],ver[N],nxt[N],edge[N];

 int f[N][N],n,m;//在i节点，选j个用户的最大收益

 int tot;

 inline void add(int x,int y,int z)

 {

     ver[++tot]=y; nxt[tot]=head[x]; head[x]=tot; edge[tot]=z;

 }

 int dfs(int x)

 {

     if(x>n-m) return ;

     int son();

     for(res i(head[x]) ; i ; i=nxt[i])

     {

         int y=ver[i];

         int tmp=dfs(y); son+=tmp;

         for(res j(son) ; j> ; j--)

             for(res k() ; k<=tmp ; k++)

                 if(k<=j)

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

     }

     return son;

 }

 int main()

 {

     n=read(); m=read();

     for(res x() ; x<=n-m ; x++)

     {

         int siz=read();

         for(res i() ; i<=siz ; i++)

         {

             int y=read(),z=read();

             add(x,y,z);

         }

     }

     memset(f,~0x3f,sizeof(f));

     for(res i() ; i<=n ; i++)

         f[i][]=;

     for(res i(n-m+) ; i<=n ; i++)

         f[i][]=read();

     dfs();

     for(res i(m) ; i>= ; i--)

         if(f[][i]>=)

             return printf("%d\n",i),;

     return ;

 }