企业官网建设流程全解析

P1273 有线电视网

网页链接

添加链接描述

题目描述

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

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

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

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

输入格式

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

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

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

K A 1 C 1 A 2 C 2 … A k C k K \ \ A_1 \ \ C_1 \ \ A_2 \ \ C_2 \ \ \ldots \ \ A_k \ \ C_kKA1​C1​A2​C2​…Ak​Ck​

K KK表示该转播站下接K KK个结点（转播站或用户），每个结点对应一对整数A AA与C CC，A AA表示结点编号，C CC表示从当前转播站传输信号到结点A AA的费用。

最后一行依次表示所有用户为观看比赛而准备支付的钱数。单次传输成本和用户愿意交的费用均不超过10 1010。

输出格式

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

输入输出样例 #1

输入 #1

5 3 2 2 2 5 3 2 3 2 4 3 3 4 2

输出 #1

2

输入输出样例 #2

输入 #2

5 3 2 2 2 5 3 2 3 2 4 3 4 4 2

输出 #2

3

输入输出样例 #3

输入 #3

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

输出 #3

5

说明/提示

样例解释

如图所示，共有五个结点。结点 ① 为根结点，即现场直播站，② 为一个中转站，③④⑤ 为用户端，共M MM个，编号从N − M + 1 N-M+1N−M+1到N NN，他们为观看比赛分别准备的钱数为3 33、4 44、2 22。

从结点 ① 可以传送信号到结点 ②，费用为2 22；

也可以传送信号到结点 ⑤，费用为3 33（第二行数据所示）；

从结点 ② 可以传输信号到结点 ③，费用为2 22；

也可传输信号到结点 ④，费用为3 33（第三行数据所示）。

如果要让所有用户（③④⑤）都能看上比赛，则信号传输的总费用为：2 + 3 + 2 + 3 = 10 2+3+2+3=102+3+2+3=10，大于用户愿意支付的总费用3 + 4 + 2 = 9 3+4+2=93+4+2=9，有线电视网就亏本了，而只让 ③④ 两个用户看比赛就不亏本了。

解题思路

本题是树形依赖背包的经典问题。有线电视网是一棵以 1 为根的树，叶子节点是用户终端，每个用户愿意支付一定费用，而每条边有传输成本。需要选择性地向部分用户传输信号，使得在不亏本（总收益 ≥ 总成本）的前提下，观看的用户数量最多。

1. 问题等价转化

• 将每个用户愿意支付的费用视为正收益，每条边的传输费用视为负成本。
• 对于每个节点u uu，若选择向其子树中的某些用户传输信号，则必须支付从u uu到这些用户的路径上的所有边成本，并累加这些用户支付的费用。
• 目标：在根节点 1 处，选择一个用户集合，使得总利润（用户支付总额 − 边成本总额）≥ 0，且用户数量最大。
• 定义f[u][j]表示以u uu为根的子树中，选择j jj个用户时能获得的最大利润。最终答案是最大的j jj，使得f[1][j] >= 0。

2. 动态规划设计

• 节点分类：
  • 若u uu是用户终端（u > N − M u > N-Mu>N−M），则f[u][1] = 用户支付费用，f[u][0] = 0。
  • 若u uu是转播站，则需要合并其所有子节点的背包结果。
• 转移方程：
  对于转播站u uu，初始f[u][0] = 0，其余为负无穷。遍历每个子节点v vv（边成本为w ww），将v vv的背包合并到u uu：
  f [ u ] [ j ] = max ⁡ k = 0 j ( f [ u ] [ j − k ] + f [ v ] [ k ] − w ) f[u][j] = \max_{k=0}^{j} \big( f[u][j-k] + f[v][k] - w \big)f[u][j]=k=0maxj​(f[u][j−k]+f[v][k]−w)
  其中k kk是从子节点v vv中选择的用户数，减去边成本w ww是因为选择v vv子树中任何用户都必须支付这条边的费用。
• 边界：对于用户终端，f[u][1] = 支付费用；对于转播站，初始只有f[u][0] = 0。

3. 算法实现（代码思路解析）

代码采用了一种后序遍历 + 一维背包合并的写法：

1. 建图：读入每个转播站的下接节点及边成本，用邻接表存储。同时将边成本记为子节点的负收益c[v] = -w。对于用户终端，读入其支付费用并累加到c[u]。
2. DFS 后序遍历：从根节点 1 开始 DFS，计算每个节点的子树大小sz[u]，并将节点按后序顺序存入数组idx（即先处理完所有子节点，再处理父节点）。
3. 动态规划：
   • 使用f[i][j]表示处理到后序数组第i ii个节点时，选择j jj个用户的最大利润。
   • 对于第i ii个节点u uu：
     • 若u uu是用户终端：f[i][j] = max(f[i-1][j-1] + c[u], f[i-1][j])（选择或不选择该用户）。
     • 若u uu是转播站：f[i][j] = max(f[i-1][j] + c[u], f[i-sz[u]][j])。这里f[i-1][j] + c[u]表示将u uu的收益（即连接到父节点的边成本负值）计入，并继承之前的状态；f[i-sz[u]][j]表示跳过整个u uu的子树（因为后序中u uu的子树是连续的，sz[u]是子树大小）。
   • 这种写法将树形背包压缩为一维后序序列上的 0/1 背包，避免了显式的子树合并循环。
4. 答案：从m mm到 0 遍历，找到第一个满足f[tot][i] >= 0的i ii，即为最多可观看的用户数。

4. 复杂度分析

• 时间复杂度：DFS 遍历O ( N ) O(N)O(N)。动态规划部分，对于每个节点u uu，枚举用户数j jj从 1 到m mm，总状态数O ( N × M ) O(N \times M)O(N×M)。N ≤ 3000 N \le 3000N≤3000，M ≤ N − 1 M \le N-1M≤N−1，最坏约9 × 10 6 9 \times 10^69×106次操作，完全可行。
• 空间复杂度：需要存储邻接表、DP 数组f[N][M]、后序数组等，O ( N × M ) O(N \times M)O(N×M)，约9 × 10 6 9 \times 10^69×106个long long，在 256M 限制内。

总结

本题是树形依赖背包的典型应用。通过后序遍历将树结构展开为序列，并利用子树在序列中连续的性质，将树形背包转化为一维序列上的背包问题，简化了状态转移。最终在根节点处寻找利润非负的最大用户数。该方法巧妙且高效，适合本题的数据规模。

代码内容

#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=3010;constll INF=1e9;constll M=1e6+10;constll mod=1e9+7;structnode{ll to,nxt;}e[N];ll n,m,cnt,head[N],c[N];voidadd(ll u,ll v){e[++cnt].to=v;e[cnt].nxt=head[u];head[u]=cnt;}ll f[N][N],idx[N],sz[N],tot;voiddfs(ll u){sz[u]=1;for(ll i=head[u];i;i=e[i].nxt){ll v=e[i].to;dfs(v);sz[u]+=sz[v];}idx[++tot]=u;}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);scanf("%lld%lld",&n,&m);for(ll u=1;u<=n-m;u++){ll k;scanf("%lld",&k);for(ll j=1;j<=k;j++){ll v;scanf("%lld",&v);ll w;scanf("%lld",&w);c[v]=-w;add(u,v);}}for(ll u=n-m+1;u<=n;u++){ll x;scanf("%lld",&x);c[u]+=x;}dfs(1);for(ll i=0;i<=tot;i++)for(ll j=1;j<=m;j++)f[i][j]=-INF;for(ll i=1;i<=tot;i++){ll u=idx[i];for(ll j=1;j<=m;j++){if(n-m+1<=u)f[i][j]=max(f[i-1][j-1]+c[u],f[i-1][j]);elsef[i][j]=max(f[i-1][j]+c[u],f[i-sz[u]][j]);}}for(ll i=m;i>=0;i--){if(f[tot][i]>=0){printf("%lld\n",i);return0;}}return0;}