题目内容

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

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

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

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

输入格式
输入文件的第一行包含两个用空格隔开的整数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的费用。最后一行依次表示所有用户为观看比赛而准备支付的钱数。

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

解题思路

树上背包

首先定义状态:发现节点的编号必须计入状态。而费用不太好计入(值域过大),选择计入最多能服务的用户数量。

f(i,u,j) 表示节点 u 的前 i 个子树中,选择 j 个叶子节点(用户)能达到的最大收益。令 vu 的一个孩子节点,s_v 表示 v 为根的子树下叶子节点的个数,则可以进行如下转移:

f(i,u,j)=\max_{k=0}^{\min\lbrace s_v,j\rbrace}\lbrace f(i-1,u,j-k)+f(s_v,v,k)-w(u,v)\rbrace

方程的意义就是在前 i-1 个子树中选取 j-k 个叶子结点,在第 i 个子树中选择 k 个叶子结点。这样可以做到不重复。

类似 0-1 背包的思路,我们可以将 i 这一维滚动掉,然后倒序枚举 j,保证调用到的 f(u,j-k)f(i-1,u,j-k)。核心转移代码如下:

dfs(v);
size[u]+=size[v];
for(int j=size[u];j>=0;j--)
    for(int k=0;k<=min(j,size[v]);k++)
        f[u][j]=max(f[u][j],f[u][j-k]+f[v][k]-w);

其他要注意的点:

  • $f(i,0)$ 要初始化成 0,因为一个用户都不服务的话费用就是 0
  • 其他的 f(u,j) 要初始化成负无穷,实现可以 memset(f,0x8f,sizeof f);
#include <cstdio>
#include <cctype>
#include <vector> 
#include <cstring>

inline int read()
{
    char c = getchar();
    int s = 0;
    while (!isdigit(c))
        c = getchar();
    while (isdigit(c))
        s = 10 * s + c - '0', c = getchar();
    return s;
}

inline int max(int a,int b)
{
    return a>b?a:b;
}

inline int min(int a,int b)
{
    return a<b?a:b;
}

struct edge
{
    int to,w;
    edge(){}
    edge(int _to,int _w)
    {
        to=_to;
        w=_w;
    }
};

const int maxn=3015;
std::vector<edge> G[maxn];
int n,m,f[maxn][maxn],size[maxn];

void dfs(int u)
{
    if(u>n-m)
        return;
    for(auto i:G[u])
    {
        int v=i.to,w=i.w;
        dfs(v);
        size[u]+=size[v];
        for(int j=size[u];j>=0;j--)
            for(int k=0;k<=min(j,size[v]);k++)
                f[u][j]=max(f[u][j],f[u][j-k]+f[v][k]-w);
    }
    return;
}

int main()
{
    n=read(),m=read();
    memset(f,0x8f,sizeof f);
    //printf("%d\n",f[1][1]);
    for(int i=1;i<=n-m;i++)
    {
        f[i][0]=0;
        int k=read(),A,C;
        while(k--)
        {
            A=read(),C=read();
            G[i].push_back(edge(A,C));
        }
    }
    for(int i=n-m+1;i<=n;i++)
    {
        f[i][1]=read();
        f[i][0]=0;
        size[i]=1;
    }
    dfs(1);
    for(int i=m;i>=0;i--)
        if(f[1][i]>=0)
        {
            printf("%d\n",i);
            return 0;
        }
}
最后修改日期:2020年9月14日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。