当前位置: 首页 > news >正文

解题报告-洛谷P1273 有线电视网

P1273 有线电视网

题目描述

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

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

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

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

输入格式

输入文件的第一行包含两个用空格隔开的整数 \(N\)\(M\),其中 \(2 \le N \le 3000\)\(1 \le M \le N-1\)\(N\) 为整个有线电视网的结点总数,\(M\) 为用户终端的数量。

第一个转播站即树的根结点编号为 \(1\),其他的转播站编号为 \(2\)\(N-M\),用户终端编号为 \(N-M+1\)\(N\)

接下来的 \(N-M\) 行每行表示—个转播站的数据,第 \(i+1\) 行表示第 \(i\) 个转播站的数据,其格式如下:

\(K \ \ A_1 \ \ C_1 \ \ A_2 \ \ C_2 \ \ \ldots \ \ A_k \ \ C_k\)

\(K\) 表示该转播站下接 \(K\) 个结点(转播站或用户),每个结点对应一对整数 \(A\)\(C\)\(A\) 表示结点编号,\(C\) 表示从当前转播站传输信号到结点 \(A\) 的费用。最后一行依次表示所有用户为观看比赛而准备支付的钱数。单次传输成本和用户愿意交的费用均不超过 \(10\)

输出格式

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

输入输出样例 #1

输入 #1

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

输出 #1

2

说明/提示

样例解释

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

从结点 ① 可以传送信号到结点 ②,费用为 \(2\)

也可以传送信号到结点 ⑤,费用为 \(3\)(第二行数据所示);

从结点 ② 可以传输信号到结点 ③,费用为\(2\)

也可传输信号到结点 ④,费用为 \(3\)(第三行数据所示)。

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


解题报告

应该算是P2014 CTSC1997] 选课 - 洛谷的加强版吧。

显然是个树上背包问题,先考虑怎么设状态数组。一开始的时候想设 \(dp[u][j]\) 表示在根为节点 \(u\) 的子树中利润为 \(j\) 时的最大人数,后来发现这样不太好转移,而且似乎需要多个辅助数组去实现,就放弃了这个状态设计。

转化一下思路:我们可以设 \(dp[u][i]\) 表示在以点 \(u\) 根的子树中选择 \(i\) 个用户时的最大利润,这样在最后寻找答案时,只需要用 \(i\)\(m\) 开始倒序扫描 \(dp[1][i]\),找到第一个 \(i\) 使得 \(dp[1][i] \geq 0\),输出这个 \(i\) 就可以了。

统计答案的事解决了,应该来具体解决状态转移的问题。

先给出方程:设当前节点为 \(u\),所拥有的用户为 \(i\),其子节点为 \(v\),所用的用户为 \(j\),从 \(u\)\(v\) 的边权为 \(e_{u,v}\),则有以下转移。

\[dp[u][i]=\max_{v \in son(u)} dp[u][i-j]+dp[v][j]-e_{u,v} \]

对于叶节点 \(t\),则有:

\[dp[t][1]=w_t \]

其中 \(w_t\) 表示用户 \(t\) 愿意支付的金额。

还需要考虑边界的问题:显然,\(cnt_u\) 表示以点 \(u\) 为根的子树中用户(即叶节点)的总数,对于上式中的 \(i\)\(j\),有 \(i \leq cnt_u\)\(j \leq cnt_v\),同时也不能在 \(v\) 的子树中选出比 \(u\) 的子树还多的用户,所以有 \(j \leq i\)

同时,因为可能有负的利润,所以要把 dp 数组初始化为 \(+\infty\),并把每个点 \(i\)\(dp[i][0]\) 赋值为 \(0\)

复杂度为 \(O(nm^2)\),代码如下:

#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
const int N=3110;#define ckmax(x,y) ( x=max(x,y) )
#define ckmin(x,y) ( x=min(x,y) )inline int read()
{int f=1,x=0; char ch=getchar();while(!isdigit(ch)) { if(ch=='-') f=-1; ch=getchar(); }while(isdigit(ch))  { x=x*10+ch-'0';    ch=getchar(); }return f*x;
}int n,m,w[N],W;
int dp[N][N];
int cnt[N];struct edge
{int next,to;int dis;
}e[N<<1];
int head[N],tot;void add_edge(int u,int v,int w)
{e[++tot]=(edge){ head[u],v,w };head[u]=tot;e[++tot]=(edge){ head[v],u,w };head[v]=tot;
}void dfs(int u,int fa)
{if(w[u]){dp[u][cnt[u]=1]=w[u];return ;}for(int k=head[u];k;k=e[k].next){int v=e[k].to;if(v==fa) continue;dfs(v,u);cnt[u]+=cnt[v];for(int i=cnt[u];i>0;i--)for(int j=1;j<=min(i,cnt[v]);j++)ckmax(dp[u][i],dp[u][i-j]+dp[v][j]-e[k].dis);}
}signed main()
{// freopen("P1273.in","r",stdin);// freopen("P1273.out","w",stdout);n=read(),m=read();for(int i=1;i<=n-m;i++){int k=read();for(int j=1;j<=k;j++){int p=read(),w=read();add_edge(i,p,w);}}for(int i=1;i<=m;i++)w[n-m+i]=read();memset(dp,-0x3f,sizeof(dp));for(int i=1;i<=n;i++) dp[i][0]=0;dfs(1,0);for(int i=m;i>0;i--)if(dp[1][i]>=0){printf("%d",i);break;}return 0;
}
http://www.sczhlp.com/news/68673/

相关文章:

  • acl
  • 重生之从零开始的神经网络算法学习之路——第六篇 初识PyTorch(环境搭建和使用GPU计算)
  • 具身智能基础技术路线
  • 安徽网站设计费用国外产品设计网
  • 深圳优化网站排名教做年糕博客网站
  • 国家级示范校建设专题网站湖北营销型网站建设
  • 网站设计软件有哪些wordpress收发邮件功能
  • 个人官方网站怎么建设温州网站建设策划方案
  • 邢台网站网页设计公司软件开发工程师英文
  • 营销型网站如何制作制作微网站的费用
  • 厦门免费自助建站模板铁岭新区旅行社电话
  • 网站seo报表p2p网站建设费用
  • 用asp做网站遇到的问题微商城网站建设服务
  • 做玻璃的网站安阳县交易中心网站建设招标
  • 俄罗斯视频网站开发怎么装字体到wordpress
  • 写一个自动化鼠标,键盘调用程序
  • 写一个提取word所有表格的程序
  • 写一个NVIDIA canvas使用教程
  • 探索MZGantt:高效项目管理的甘特图解决方案
  • 蓄电池能量管理系统的MATLAB/Simulink仿真
  • 怎样网站制作设计室内设计需要什么学历
  • 湖南网站建设公司 都来磐石网络沈阳线上教学
  • 社区网站建设工作职责做网站vpn多大内存
  • 企业网站 数据库wordpress plugins权限
  • 部署Oracle (11.2.0.1.0)
  • find_code最终版
  • 页面简洁的网站国外机械做的好的网站
  • 黄骅的网站工信部网站icp备案查询
  • 网站推广 扬州游戏门户网站开发资源
  • 百度怎么制作网站教程沈阳网站建设服务电话