Poj 1155 无线电（树形DP）

A TV-network plans to broadcast an important football match. Their network of transmitters and users can be represented as a tree. The root of the tree is a transmitter that emits the football match, the leaves of the tree are the potential users and other vertices in the tree are relays (transmitters).

The price of transmission of a signal from one transmitter to another or to the user is given. A price of the entire broadcast is the sum of prices of all individual signal transmissions.

Every user is ready to pay a certain amount of money to watch the match and the TV-network then decides whether or not to provide the user with the signal.

Write a program that will find the maximal number of users able to watch the match so that the TV-network's doesn't lose money from broadcasting the match.

Input

The first line of the input file contains two integers N and M, 2 <= N <= 3000, 1 <= M <= N-1, the number of vertices in the tree and the number of potential users.

The root of the tree is marked with the number 1, while other transmitters are numbered 2 to N-M and potential users are numbered N-M+1 to N.

The following N-M lines contain data about the transmitters in the following form:

K A1 C1 A2 C2 ... AK CK

Means that a transmitter transmits the signal to K transmitters or users, every one of them described by the pair of numbers A and C, the transmitter or user's number and the cost of transmitting the signal to them.

The last line contains the data about users, containing M integers representing respectively the price every one of them is willing to pay to watch the match.

Output

The first and the only line of the output file should contain the maximal number of users described in the above text.

Sample Input

9 6

3 2 2 3 2 9 3

2 4 2 5 2

3 6 2 7 2 8 2

4 3 3 3 1 1

Sample Output

5

翻译：一家电视网计划播放一场重要的足球比赛。它们的广播站中转站和用户网络可以表示为树。树的根是发送足球比赛的广播站，树的叶子节点是潜在用户，树中的其他节点是中转站。

给出了从一个中转站或广播站向另一个中转站向用户传输信号的价格。整个广播的价格是所有选择的传播路径的价格之和。 每个用户都准备好支付一定的钱观看比赛，然后电视网络决定是否向用户提供信号。写一个能找到最多观看比赛用户的节目，这样电视网就不会因为转播比赛而损失金钱。

这是一道树形dp的题目，给我们n表示节点（电视台为1+中转站+用户个数）个数，m表示用户个数，n是大于m的。先输入n和m，然后剩下的n-m行按k a1 c1 a2 c2 …ak ck输入的是每个除了观众之外的的节点以及他们连接的权值。之后输入从每个用户可以赚到的钱。

要我们求出，在不亏本的条件下，最多能有多少观众。

状态转移是dp[v][j]=max(dp[v][j],dp[u][j-k]+dp[v][k]-w(root,v))

u表示父节点,v表示的是子节点，u表示父节点之下有几个观众，v表示这个子节点之下有几个观众，w(root,v)表示root到v的权值。那么dp[v][j]就表示在v这个节点之下有j个观众最大的值是多少。

这是两个初始情况:

节点观众为0的时候dp[i][0]=0;

节点观众为1的时候dp[i][1]=val[i];

dfs(root)

当root是观众结点的时候，初始化这个dp[root][1]=val[I]

去试探每个子节点，储存父节点和子节点各自包含的观众数，然后用状态转移得出dp的值

#include<iostream>
#include<cstring>
#include<vector>
#define mem(s,t) memset(s,t,sizeof(s))

struct node
{
    int v,w;
    node(int a,int b):v(a),w(b){

    }
} ;//到目标节点v的价格为w
using namespace std;
vector<node>G[3005];
int money[3005];
int dp[3005][3005];
int n,m;

int dfs(int root)
{

    if(root>n-m)//用来判断是不是观众节点
    {

        dp[root][1]=money[root];
        return 1;
    }
    int sum=0;
    for(int i=0;i<G[root].size();i++){//枚举每个与之相连的子节点
        int v=G[root][i].v;
        int t=dfs(v);//子节点的观众数
        sum+=t;//父节点的观众数
        for(int j=sum;j>0;j--)
            for(int k=1;k<=t;++k)
            {
                if(j-k>=0)
                dp[root][j]=max(dp[root][j],dp[root][j-k]+dp[v][k]-G[root][i].w);
            }
    }

    return sum;
}
int main()
{
    using namespace std;
    while(cin>>n>>m)
    {
        int t;
        for(int i=1;i<=n-m;i++){
        cin>>t;
        for(int z=1;z<=t;z++)//用vector输入每个非观众节点的子节点
        {
            int a,c;
            cin>>a>>c;
            G[i].push_back(node(a,c));
        }
        }

        mem(dp,-0x3f);//用了宏定义了的~
        for(int i=n-m+1;i<=n;i++){
            cin>>money[i];
        }
        for(int i=1;i<=n;i++)dp[i][0]=0; //初始化节点观众为0的情况
        dfs(1);
        for(int i=m;i>=1;--i)//要寻找不亏钱的最多观众就可以从m递减去寻找dp大于0的值
        {
            if(dp[1][i]>=0){
                printf("%d",i);
                break;
            }
        }
    }
}