P1273 有线电视网网页链接添加链接描述题目描述某收费有线电视网计划转播一场重要的足球比赛。他们的转播网和用户终端构成一棵树状结构这棵树的根结点位于足球比赛的现场树叶为各个用户终端其他中转站为该树的内部节点。从转播站到转播站以及从转播站到所有用户终端的信号传输费用都是已知的一场转播的总费用等于传输信号的费用总和。现在每个用户都准备了一笔费用想观看这场精彩的足球比赛有线电视网有权决定给哪些用户提供信号而不给哪些用户提供信号。写一个程序找出一个方案使得有线电视网在不亏本的情况下使观看转播的用户尽可能多。输入格式输入文件的第一行包含两个用空格隔开的整数N NN和M MM其中2 ≤ N ≤ 3000 2 \le N \le 30002≤N≤30001 ≤ M ≤ N − 1 1 \le M \le N-11≤M≤N−1N NN为整个有线电视网的结点总数M MM为用户终端的数量。第一个转播站即树的根结点编号为1 11其他的转播站编号为2 22到N − M N-MN−M用户终端编号为N − M 1 N-M1N−M1到N NN。接下来的N − M N-MN−M行每行表示—个转播站的数据第i 1 i1i1行表示第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_kKA1C1A2C2…AkCkK KK表示该转播站下接K KK个结点转播站或用户每个结点对应一对整数A AA与C CCA AA表示结点编号C CC表示从当前转播站传输信号到结点A AA的费用。最后一行依次表示所有用户为观看比赛而准备支付的钱数。单次传输成本和用户愿意交的费用均不超过10 1010。输出格式输出文件仅一行包含一个整数表示上述问题所要求的最大用户数。输入输出样例 #1输入 #15 3 2 2 2 5 3 2 3 2 4 3 3 4 2输出 #12输入输出样例 #2输入 #25 3 2 2 2 5 3 2 3 2 4 3 4 4 2输出 #23输入输出样例 #3输入 #39 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输出 #35说明/提示样例解释如图所示共有五个结点。结点 ① 为根结点即现场直播站② 为一个中转站③④⑤ 为用户端共M MM个编号从N − M 1 N-M1N−M1到N NN他们为观看比赛分别准备的钱数为3 33、4 44、2 22。从结点 ① 可以传送信号到结点 ②费用为2 22也可以传送信号到结点 ⑤费用为3 33第二行数据所示从结点 ② 可以传输信号到结点 ③费用为2 22也可传输信号到结点 ④费用为3 33第三行数据所示。如果要让所有用户③④⑤都能看上比赛则信号传输的总费用为2 3 2 3 10 232310232310大于用户愿意支付的总费用3 4 2 9 34293429有线电视网就亏本了而只让 ③④ 两个用户看比赛就不亏本了。解题思路本题是树形依赖背包的经典问题。有线电视网是一棵以 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-MuN−M则f[u][1] 用户支付费用f[u][0] 0。若u uu是转播站则需要合并其所有子节点的背包结果。转移方程对于转播站u uu初始f[u][0] 0其余为负无穷。遍历每个子节点v vv边成本为w ww将v vv的背包合并到u uuf [ u ] [ j ] max k 0 j ( f [ u ] [ j − k ] f [ v ] [ k ] − w ) f[u][j] \max_{k0}^{j} \big( f[u][j-k] f[v][k] - w \big)f[u][j]k0maxj(f[u][j−k]f[v][k]−w)其中k kk是从子节点v vv中选择的用户数减去边成本w ww是因为选择v vv子树中任何用户都必须支付这条边的费用。边界对于用户终端f[u][1] 支付费用对于转播站初始只有f[u][0] 0。3. 算法实现代码思路解析代码采用了一种后序遍历 一维背包合并的写法建图读入每个转播站的下接节点及边成本用邻接表存储。同时将边成本记为子节点的负收益c[v] -w。对于用户终端读入其支付费用并累加到c[u]。DFS 后序遍历从根节点 1 开始 DFS计算每个节点的子树大小sz[u]并将节点按后序顺序存入数组idx即先处理完所有子节点再处理父节点。动态规划使用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 背包避免了显式的子树合并循环。答案从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≤3000M ≤ 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 限制内。总结本题是树形依赖背包的典型应用。通过后序遍历将树结构展开为序列并利用子树在序列中连续的性质将树形背包转化为一维序列上的背包问题简化了状态转移。最终在根节点处寻找利润非负的最大用户数。该方法巧妙且高效适合本题的数据规模。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N3010;constll INF1e9;constll M1e610;constll mod1e97;structnode{ll to,nxt;}e[N];ll n,m,cnt,head[N],c[N];voidadd(ll u,ll v){e[cnt].tov;e[cnt].nxthead[u];head[u]cnt;}ll f[N][N],idx[N],sz[N],tot;voiddfs(ll u){sz[u]1;for(ll ihead[u];i;ie[i].nxt){ll ve[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 u1;un-m;u){ll k;scanf(%lld,k);for(ll j1;jk;j){ll v;scanf(%lld,v);ll w;scanf(%lld,w);c[v]-w;add(u,v);}}for(ll un-m1;un;u){ll x;scanf(%lld,x);c[u]x;}dfs(1);for(ll i0;itot;i)for(ll j1;jm;j)f[i][j]-INF;for(ll i1;itot;i){ll uidx[i];for(ll j1;jm;j){if(n-m1u)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 im;i0;i--){if(f[tot][i]0){printf(%lld\n,i);return0;}}return0;}
P1273 有线电视网网页链接添加链接描述题目描述某收费有线电视网计划转播一场重要的足球比赛。他们的转播网和用户终端构成一棵树状结构这棵树的根结点位于足球比赛的现场树叶为各个用户终端其他中转站为该树的内部节点。从转播站到转播站以及从转播站到所有用户终端的信号传输费用都是已知的一场转播的总费用等于传输信号的费用总和。现在每个用户都准备了一笔费用想观看这场精彩的足球比赛有线电视网有权决定给哪些用户提供信号而不给哪些用户提供信号。写一个程序找出一个方案使得有线电视网在不亏本的情况下使观看转播的用户尽可能多。输入格式输入文件的第一行包含两个用空格隔开的整数N NN和M MM其中2 ≤ N ≤ 3000 2 \le N \le 30002≤N≤30001 ≤ M ≤ N − 1 1 \le M \le N-11≤M≤N−1N NN为整个有线电视网的结点总数M MM为用户终端的数量。第一个转播站即树的根结点编号为1 11其他的转播站编号为2 22到N − M N-MN−M用户终端编号为N − M 1 N-M1N−M1到N NN。接下来的N − M N-MN−M行每行表示—个转播站的数据第i 1 i1i1行表示第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_kKA1C1A2C2…AkCkK KK表示该转播站下接K KK个结点转播站或用户每个结点对应一对整数A AA与C CCA AA表示结点编号C CC表示从当前转播站传输信号到结点A AA的费用。最后一行依次表示所有用户为观看比赛而准备支付的钱数。单次传输成本和用户愿意交的费用均不超过10 1010。输出格式输出文件仅一行包含一个整数表示上述问题所要求的最大用户数。输入输出样例 #1输入 #15 3 2 2 2 5 3 2 3 2 4 3 3 4 2输出 #12输入输出样例 #2输入 #25 3 2 2 2 5 3 2 3 2 4 3 4 4 2输出 #23输入输出样例 #3输入 #39 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输出 #35说明/提示样例解释如图所示共有五个结点。结点 ① 为根结点即现场直播站② 为一个中转站③④⑤ 为用户端共M MM个编号从N − M 1 N-M1N−M1到N NN他们为观看比赛分别准备的钱数为3 33、4 44、2 22。从结点 ① 可以传送信号到结点 ②费用为2 22也可以传送信号到结点 ⑤费用为3 33第二行数据所示从结点 ② 可以传输信号到结点 ③费用为2 22也可传输信号到结点 ④费用为3 33第三行数据所示。如果要让所有用户③④⑤都能看上比赛则信号传输的总费用为2 3 2 3 10 232310232310大于用户愿意支付的总费用3 4 2 9 34293429有线电视网就亏本了而只让 ③④ 两个用户看比赛就不亏本了。解题思路本题是树形依赖背包的经典问题。有线电视网是一棵以 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-MuN−M则f[u][1] 用户支付费用f[u][0] 0。若u uu是转播站则需要合并其所有子节点的背包结果。转移方程对于转播站u uu初始f[u][0] 0其余为负无穷。遍历每个子节点v vv边成本为w ww将v vv的背包合并到u uuf [ u ] [ j ] max k 0 j ( f [ u ] [ j − k ] f [ v ] [ k ] − w ) f[u][j] \max_{k0}^{j} \big( f[u][j-k] f[v][k] - w \big)f[u][j]k0maxj(f[u][j−k]f[v][k]−w)其中k kk是从子节点v vv中选择的用户数减去边成本w ww是因为选择v vv子树中任何用户都必须支付这条边的费用。边界对于用户终端f[u][1] 支付费用对于转播站初始只有f[u][0] 0。3. 算法实现代码思路解析代码采用了一种后序遍历 一维背包合并的写法建图读入每个转播站的下接节点及边成本用邻接表存储。同时将边成本记为子节点的负收益c[v] -w。对于用户终端读入其支付费用并累加到c[u]。DFS 后序遍历从根节点 1 开始 DFS计算每个节点的子树大小sz[u]并将节点按后序顺序存入数组idx即先处理完所有子节点再处理父节点。动态规划使用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 背包避免了显式的子树合并循环。答案从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≤3000M ≤ 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 限制内。总结本题是树形依赖背包的典型应用。通过后序遍历将树结构展开为序列并利用子树在序列中连续的性质将树形背包转化为一维序列上的背包问题简化了状态转移。最终在根节点处寻找利润非负的最大用户数。该方法巧妙且高效适合本题的数据规模。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N3010;constll INF1e9;constll M1e610;constll mod1e97;structnode{ll to,nxt;}e[N];ll n,m,cnt,head[N],c[N];voidadd(ll u,ll v){e[cnt].tov;e[cnt].nxthead[u];head[u]cnt;}ll f[N][N],idx[N],sz[N],tot;voiddfs(ll u){sz[u]1;for(ll ihead[u];i;ie[i].nxt){ll ve[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 u1;un-m;u){ll k;scanf(%lld,k);for(ll j1;jk;j){ll v;scanf(%lld,v);ll w;scanf(%lld,w);c[v]-w;add(u,v);}}for(ll un-m1;un;u){ll x;scanf(%lld,x);c[u]x;}dfs(1);for(ll i0;itot;i)for(ll j1;jm;j)f[i][j]-INF;for(ll i1;itot;i){ll uidx[i];for(ll j1;jm;j){if(n-m1u)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 im;i0;i--){if(f[tot][i]0){printf(%lld\n,i);return0;}}return0;}
平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测)
