poj1155 TELE(树形dp)然而tip

60 阅读 0 评论 40 点赞

我是靠谱客的博主幸福睫毛膏，最近开发中收集的这篇文章主要介绍poj1155 TELE(树形dp)然而tip，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Description

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

分析：
画出一棵树来研究一下：
这里写图片描述

这就让我想起了这道题

于是我又开始yy了
f[i][j]表示选择节点i,ta及ta的子树中的价值为j时最大的被选择节点数
枚举j，那么i的儿子们就可以自由的分配j，但是j的范围我们完全无法掌控
显然这种状态不行

实际上我们不用特意去卡这个>=0的限制，
我们可以直接找到最大值
最后在寻找答案的时候只要扫一下 f[1][j] 就可以了

f[i][j]表示i这颗子树中，选择j个节点得到的最大利润
size[i]表示i这颗子树中所有用户的数量
每次枚举i的一个儿子中选取的节点数量
进行转移：f[i][j]=max{f[i][j-k]+f[son][k]-way[i].v}

然而

不能就这么simple的用f转移了
我们需要提前记录下选完上一个儿子后的状态
更新只能是在上一个儿子的基础上，而不能是当前的儿子的选择不断的叠加
有一点像背包的思想

tip

这种转移需要另一个数组记录的情况
以前也做到过，以后都要注意
如果一个状态可以从多个状态转移而来，
然而这些状态又不能重叠
这个时候就要考虑用另一个数组记录一下

这里写代码片
#include<cstdio>
#include<cstring>
#include<iostream>

using namespace std;

const int O=1000;
const int N=3010;
struct node{
    int x,y,v,nxt;
};
node way[N<<1];
int n,m,pay[N],st[N],tot=0;
int f[N][N],size[N],g[N],l[N];

void add(int u,int w,int z)
{
    tot++;
    way[tot].x=u;way[tot].y=w;way[tot].v=z;way[tot].nxt=st[u];st[u]=tot;
}

void dfs(int now)
{
    if (now>n-m)
    {
        size[now]=1;
        return;
    }
    for (int i=st[now];i;i=way[i].nxt)
    {       
        dfs(way[i].y);
        size[now]+=size[way[i].y];
    }
}

void doit(int now)
{
    if (now>n-m)
    {
        f[now][0]=0;
        f[now][1]=pay[now];
        return;
    }
    f[now][0]=0;
    for (int i=st[now];i;i=way[i].nxt)
    {
        int y=way[i].y;
        doit(y);
        for (int k=size[now];k>=0;k--) l[k]=f[now][k];  //先提前记录下选完上一个儿子后的状态
        for (int k=size[y];k>=0;k--)
        {
            for (int j=size[now];j>=0;j--) g[j]=l[j];
            //更新只能是在上一个儿子的基础上，而不能是当前的儿子的选择不断的叠加  
            for (int j=size[now];j>=k;j--) g[j]=max(g[j],g[j-k]+f[y][k]-way[i].v);
            for (int j=size[now];j>=0;j--) f[now][j]=max(f[now][j],g[j]);
        }
    }
}

int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n-m;i++)
    {
        int k;
        scanf("%d",&k);
        for (int j=1;j<=k;j++)
        {
            int u,z;
            scanf("%d%d",&u,&z);
            add(i,u,z);
        }
    }
    for (int i=1;i<=m;i++) scanf("%d",&pay[n-m+i]);
    dfs(1);
    memset(f,128,sizeof(f));
    memset(g,128,sizeof(g));
    doit(1);
    for (int i=size[1];i>=0;i--) 
        if (f[1][i]>=0)
        {
            printf("%d",i);
            break;
        }
    return 0;
}