注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

TsReaper的博客

一起来玩算法竞赛吧~

 
 
 
 
 

日志

 
 

[题解]有线电视网  

2015-08-04 18:31:38|  分类: 题解 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
关键字:树形dp,背包。

Link&Limit


        [洛谷1273]
        时间限制:1000ms  空间限制:131072kb

Description


        某收费有线电视网计划转播一场重要的足球比赛。他们的转播网和用户终端构成一棵树状结构,这棵树的根结点位于足球比赛的现场,树叶为各个用户终端,其他中转站为该树的内部节点。
从转播站到转播站以及从转播站到所有用户终端的信号传输费用都是已知的,一场转播的总费用等于传输信号的费用总和。
        现在每个用户都准备了一笔费用想观看这场精彩的足球比赛,有线电视网有权决定给哪些用户提供信号而不给哪些用户提供信号。
        写一个程序找出一个方案使得有线电视网在不亏本的情况下使观看转播的用户尽可能多。

Input Format


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

Output Format


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

Sample Input #1


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

Sample Output #1


2

Hint


【样例解释】
[题解]有线电视网 - TsReaper - TsReaper的博客
        如图所示,共有五个结点。结点①为根结点,即现场直播站,②为一个中转站,③④⑤为用户端,共M个,编号从N-M+1到N,他们为观看比赛分别准备的钱数 为3、4、2,从结点①可以传送信号到结点②,费用为2,也可以传送信号到结点⑤,费用为3(第二行数据所示),从结点②可以传输信号到结点③,费用为 2。也可传输信号到结点④,费用为3(第三行数据所示),如果要让所有用户(③④⑤)都能看上比赛,则信号传输的总费用为:2+3+2+3=10,大于用户愿意支付的总费用3+4+2=9,有线电视网就亏本了,而只让③④两个用户看比赛就不亏本了。

        树上的背包。对于某一个点,它的每个儿子都能被看作一类物品,该类物品能取0,1,2,...num个(num是以该儿子为根的子树有多少叶子节点)。我们算出每个点供应0~num个用户能获得的最大利润。最后在根节点中查找,最大的利润≥0的用户数就是答案。
        虽然分析起来似乎是一个O(n^3)的算法,但是由于无效的状态比较多,可以AC。

#include <stdio.h>
#include <string.h>
int n,m,f[3010][3010],pay[3010];
int e[3010][3],p[3010],tot = 0;
int max(int a,int b)
{
return a>b?a:b;
}
void adde(int sn,int fn,int val)
{
e[++tot][0] = fn; e[tot][1] = val; e[tot][2] = p[sn]; p[sn] = tot;
}
int dp(int sn)
{
int i,j,k,fn,val,x,sum = 0;
if(sn>n-m) { f[sn][1] = pay[sn]; return 1;}
for(i=p[sn];i;i=e[i][2])
{
fn = e[i][0]; val = e[i][1];
x = dp(fn); sum += x;
for(j=sum;j;j--) for(k=1;k<=x&&k<=j;k++) f[sn][j] = max(f[sn][j],f[sn][j-k]+f[fn][k]-val);
}
return sum;
}
int main()
{
int i,j,cnt,fn,val;
scanf("%d%d",&n,&m);
memset(f,-60,sizeof(f));
for(i=1;i<=n;i++) f[i][0] = 0;
for(i=1;i<=n-m;i++)
{
scanf("%d",&cnt);
for(j=1;j<=cnt;j++)
{
scanf("%d%d",&fn,&val);
adde(i,fn,val);
}
}
for(i=n-m+1;i<=n;i++) scanf("%d",&pay[i]);
dp(1);
for(i=m;i;i--) if(f[1][i]>=0) break;
printf("%d",i);
return 0;
}

  评论这张
 
阅读(31)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018