P1273 有线电视网(树形dp)

P1273 有线电视网

题目描述

某收费有线电视网计划转播一场重要的足球比赛。他们的转播网和用户终端构成一棵树状结构，这棵树的根结点位于足球比赛的现场，树叶为各个用户终端，其他中转站为该树的内部节点。

从转播站到转播站以及从转播站到所有用户终端的信号传输费用都是已知的，一场转播的总费用等于传输信号的费用总和。

现在每个用户都准备了一笔费用想观看这场精彩的足球比赛，有线电视网有权决定给哪些用户提供信号而不给哪些用户提供信号。

写一个程序找出一个方案使得有线电视网在不亏本的情况下使观看转播的用户尽可能多。

输入输出格式

输入格式：

输入文件的第一行包含两个用空格隔开的整数N和M，其中2≤N≤3000，1≤M≤N-1，N为整个有线电视网的结点总数，M为用户终端的数量。

第一个转播站即树的根结点编号为1，其他的转播站编号为2到N-M，用户终端编号为N-M+1到N。

接下来的N-M行每行表示—个转播站的数据，第i+1行表示第i个转播站的数据，其格式如下：

K A1 C1 A2 C2 … Ak Ck

K表示该转播站下接K个结点(转播站或用户)，每个结点对应一对整数A与C，A表示结点编号，C表示从当前转播站传输信号到结点A的费用。最后一行依次表示所有用户为观看比赛而准备支付的钱数。

输出格式：

输出文件仅一行，包含一个整数，表示上述问题所要求的最大用户数。

• 显然树形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(0),f(1); char ch;
    while(!isdigit(ch=getchar())) if(ch=='-') f=-1;
    while(isdigit(ch)) x=x*10+ch-'0',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 1;
    int son(0);
    for(res i(head[x]) ; i ; i=nxt[i])
    {
        int y=ver[i];
        int tmp=dfs(y); son+=tmp;
        for(res j(son) ; j>0 ; j--)
            for(res k(1) ; 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(1) ; x<=n-m ; x++)
    {
        int siz=read();
        for(res i(1) ; i<=siz ; i++)
        {
            int y=read(),z=read(); 
            add(x,y,z);
        }
    }
    memset(f,~0x3f,sizeof(f));
    for(res i(1) ; i<=n ; i++)    
        f[i][0]=0;
    for(res i(n-m+1) ; i<=n ; i++) 
        f[i][1]=read();
    dfs(1);
    for(res i(m) ; i>=1 ; i--)
        if(f[1][i]>=0) 
            return printf("%d
",i),0;
    return 0;
}