首页 > 代码库 > 电视转播
电视转播
题目描述：一个电视网络计划转播一场重要的足球比赛。网络中的传输点和接收点（即用户）可以表示一棵树。这棵树的根是一个传输点，它将转播比赛。树的叶节点是可能要接受这场比赛的用户（他当然可以选择不看比赛，这样就不要交款）。其他非根节点，非叶节点的中间节点为数据的中转站。将一个信号从一个传输点传到另一个传输点的花费是给定的。整个转播的费用就是每一个传输费用的总和。每一个用户（叶节点）都准备付一定的钱来看这场比赛。电视网络公司要决定是否要给这个用户提供电视信号。例如：给一个节点传输信息的花费太大，而他愿意的付款也很少时，网络公司可能选择不给他转播比赛。写一个程序，找到一个传输方案使最多的用户能看到转播比赛，且转播的费用不超过所有接收信号用户的交款。
输入格式：输入文件的第一行包含两个整数N和M(2<=N<=3000,1<=M<=N-1)。N,M表示分别表示树的节点数和想观看比赛的用户数。树的根节点用1表示，中间节点的标号为2~N-M，用户的节点标号为N-M+1~N。接下来的N-M行表示传输点的信息（依次是节点1，2……）： K A1 C1 A2 C2 …… Ak Ck 表示一个传输点将信号传给K个用户，每一个包含两个数A和C，A表示传输点或用户的节点号，C表示传输的花费。最后一行含有用户的数据，有M个整数表示他们看这场比赛愿意的付费。
输出格式：仅一行包含一个整数，最大的用户数
1.多叉转二叉方法：
#include <iostream>#include<cstdio>#include<cstring>#include<cstdlib>#include<algorithm>#define MAXN 3005using namespace std;int haveson[MAXN];int cnt[MAXN];int n,m;bool vis[MAXN];struct node{ int cost,ch[2]; node(){cost=0,ch[0]=ch[1]=0;}}tree[MAXN];int f[MAXN][MAXN];void dp(int root){ if(tree[root].ch[0]) dp(tree[root].ch[0]); else f[root][1]=max(f[root][1],tree[root].cost); if(tree[root].ch[1]) dp(tree[root].ch[1]); f[root][0]=max(f[root][0],0); if(tree[root].ch[0]) { for(int i=1;i<=cnt[root];i++) { for(int k=0;k<=i&&k<=cnt[tree[root].ch[0]];k++) f[root][i]=max(f[root][i],f[tree[root].ch[0]][k]+f[tree[root].ch[1]][i-k]+tree[root].cost); if(i<=cnt[tree[root].ch[1]]) f[root][i]=max(f[root][i],f[tree[root].ch[1]][i]); } } else { for(int i=1;i<=cnt[root];i++) {f[root][i]=max(f[root][i],f[tree[root].ch[1]][i-1]+tree[root].cost); f[root][i]=max(f[root][i],f[tree[root].ch[1]][i]); } }}void dfs(int root){ vis[root]=1; if(!tree[root].ch[0]) {cnt[root]=1; } else {dfs(tree[root].ch[0]); cnt[root]+=cnt[tree[root].ch[0]]; } if(tree[root].ch[1]) {dfs(tree[root].ch[1]); cnt[root]+=cnt[tree[root].ch[1]]; } vis[root]=0;}int main(){ int k,t1,t2; scanf("%d%d",&n,&m); memset(f,0x80,sizeof f); for(int i=0;i<=n;i++) f[i][0]=0; for(int i=1;i<=n-m;i++) { scanf("%d",&k); for(int j=1;j<=k;j++) { scanf("%d%d",&t1,&t2); if(haveson[i]) tree[haveson[i]].ch[1]=t1; else tree[i].ch[0]=t1; haveson[i]=t1; tree[t1].cost=-t2; } } for(int i=n-m+1;i<=n;i++) { scanf("%d",&t1); tree[i].cost+=t1; } dfs(1); dp(1); for(int i=m;i>=0;i--) if(f[1][i]>=0) { printf("%d\n",i); return 0; } return 0;}
2.背包方法：将dfs序搜索的节点的组合做成背包，当前访问的节点加入或不加入背包。
#include <iostream>#include<cstdio>#include<cstring>#include<cstdlib>#include<algorithm>#include<vector>#define MAXN 3005using namespace std;int cost[MAXN],cnt[MAXN];const int INF=0x80808080;vector<int> fir[MAXN];int n,m,k;bool vis[MAXN];int f[MAXN][MAXN];void dfs1(int root){ if(fir[root].size()==0){cnt[root]=1;return;} for(int i=0;i<fir[root].size();i++) { int u=fir[root][i]; dfs1(u); cnt[root]+=cnt[u]; }}void dfs2(int root){ for(int i=0;i<fir[root].size();i++) { int u=fir[root][i]; for(int j=0;j<=m;j++) { if(f[root][j]>INF) f[u][j]=f[root][j]; } if(fir[u].size()) dfs2(u); int dd=0; for(int j=0;j<=m;j++) { if(fir[u].size()==0)dd=1; else dd=0; if(f[u][j]+cost[u]>=f[root][j+dd]) f[root][j+dd]=f[u][j]+cost[u]; } }}int main(){ scanf("%d%d",&n,&m); int t1,t2; for(int i=1;i<=n-m;i++) { scanf("%d",&k); for(int j=1;j<=k;j++) { scanf("%d%d",&t1,&t2); fir[i].push_back(t1); cost[t1]=-t2; } } int tmp; for(int i=n-m+1;i<=n;i++) {scanf("%d",&tmp); cost[i]+=tmp; } memset(f,0x80,sizeof f); for(int i=0;i<=n;i++) f[i][0]=0; dfs1(1); dfs2(1); for(int i=m;i>=0;i--) if(f[1][i]>=0) { printf("%d",i); return 0; } return 0;}
3.另一种背包：
自底向上，将每棵子树做成背包，再合并子树的背包，加上父亲节点。背包合并时是N^2，总的时间复杂度是O(N^3)。然而实际运行时比第二种方法还要快。
#include <iostream>#include<cstdio>#include<cstring>#include<cstdlib>#include<vector>#define MAXN 3005const int INF=0x80808080;using namespace std;vector<int> fir[MAXN];int cnt[MAXN];int cost[MAXN],n,m,t1,t2,k;int f[MAXN][MAXN];void dfs(int root){ for(int i=0;i<fir[root].size();i++) { int u=fir[root][i]; if(fir[u].size()) dfs(u); else { f[u][1]=cost[u]; cnt[u]=1; } cnt[root]+=cnt[u]; for(int k=cnt[root];k>=0;k--) {if(f[root][k]>INF) {for(int j=0;j+k<=cnt[root]&&j<=cnt[u];j++) if(f[u][j]>INF&&f[root][j+k]<f[root][k]+f[u][j]) f[root][j+k]=f[root][k]+f[u][j]; } } } for(int i=1;i<=cnt[root];i++) if(f[root][i]>INF)f[root][i]+=cost[root];}int main(){ memset(f,0x80,sizeof f); scanf("%d%d",&n,&m); for(int i=1;i<=n-m;i++) { scanf("%d",&k); for(int j=1;j<=k;j++) { scanf("%d%d",&t1,&t2); cost[t1]=-t2; fir[i].push_back(t1); } } for(int i=n-m+1;i<=n;i++) { scanf("%d",&t1); cost[i]+=t1; } for(int i=0;i<=n;i++) f[i][0]=0; dfs(1); for(int i=m;i>=0;i--) if(f[1][i]>=0) { printf("%d",i); return 0; }}
电视转播
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。