(Luogu) P1273 有线电视网 (树型dp+分组背包)

2024-03-20 17:18

本文主要是介绍(Luogu) P1273 有线电视网 (树型dp+分组背包),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

传送门

题目描述

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

输入输出格式

输入格式:

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

输出格式:

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

输入输出样例

输入样例#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,有线电视网就亏本了,而只让③④两个用户看比赛就不亏本了。

 

解题思路:dp[i][j] 代表i节点 选j个用户 赚的钱的最大值,然后对每个节点做分组背包,首先当前节点的背包总容量相当于他的子树中的所有的用户数量,然后把该节点的每一个儿子看成一组,每组中选1~n个用户,更新方程为

dp[u][j]=max( dp[u][j],dp[u][j-t]+dp[nto][t]-nw );
//   u节点选j-t个用户 加上 选这个子节点的t个用户 减掉到这个子节点这条边的花费 取个极值

最后输出使得dp[1][i]>=0的那个最大的i即可

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<cmath>
#include<sstream>
using namespace std;
typedef long long ll;
const ll inf=0x3f3f3f3f;
const int maxn=3005;
int dp[maxn][maxn];//dp[i][j] i节点 选j个用户 赚的钱的最大值 
struct edge{int to,w;
};
vector<edge> e[maxn];
int val[maxn],n,m;
int dfs(int u){if(u>=n-m+1){dp[u][1]=val[u];return 1;}int sum=0,tpnum,nto,nw;for(int i=0;i<(int)e[u].size();++i){edge tp=e[u][i];nto=tp.to,nw=tp.w;tpnum=dfs(nto);sum+=tpnum;for(int j=sum;j>0;--j){for(int t=1;t<=tpnum;++t){if(j-t>=0)	dp[u][j]=max( dp[u][j],dp[u][j-t]+dp[nto][t]-nw );}}} return sum;
}
int main(){std::ios::sync_with_stdio(0);cin>>n>>m;int num,x,y;for(int i=1;i<=n-m;++i){cin>>num;for(int j=1;j<=num;++j){cin>>x>>y;e[i].push_back(edge{x,y});}}for(int i=n-m+1;i<=n;++i)	cin>>val[i];memset(dp,~0x3f,sizeof(dp));for(int i=0;i<maxn;++i)	dp[i][0]=0; //选0个用户赚0元 dfs(1);for(int i=m;i>=0;--i){if(dp[1][i]>=0){cout<<i<<endl;break; }}return 0;
}

 

这篇关于(Luogu) P1273 有线电视网 (树型dp+分组背包)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/830186

相关文章

【前端学习】AntV G6-08 深入图形与图形分组、自定义节点、节点动画(下)

【课程链接】 AntV G6:深入图形与图形分组、自定义节点、节点动画(下)_哔哩哔哩_bilibili 本章十吾老师讲解了一个复杂的自定义节点中,应该怎样去计算和绘制图形,如何给一个图形制作不间断的动画,以及在鼠标事件之后产生动画。(有点难,需要好好理解) <!DOCTYPE html><html><head><meta charset="UTF-8"><title>06

poj2576(二维背包)

题意:n个人分成两组,两组人数只差小于1 , 并且体重只差最小 对于人数要求恰好装满,对于体重要求尽量多,一开始没做出来,看了下解题,按照自己的感觉写,然后a了 状态转移方程:dp[i][j] = max(dp[i][j],dp[i-1][j-c[k]]+c[k]);其中i表示人数,j表示背包容量,k表示输入的体重的 代码如下: #include<iostream>#include<

hdu2159(二维背包)

这是我的第一道二维背包题,没想到自己一下子就A了,但是代码写的比较乱,下面的代码是我有重新修改的 状态转移:dp[i][j] = max(dp[i][j], dp[i-1][j-c[z]]+v[z]); 其中dp[i][j]表示,打了i个怪物,消耗j的耐力值,所得到的最大经验值 代码如下: #include<iostream>#include<algorithm>#include<

csu(背包的变形题)

题目链接 这是一道背包的变形题目。好题呀 题意:给n个怪物,m个人,每个人的魔法消耗和魔法伤害不同,求打死所有怪物所需的魔法 #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>//#include<u>#include<map

hdu4826(三维DP)

这是一个百度之星的资格赛第四题 题目链接:http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1004&cid=500 题意:从左上角的点到右上角的点,每个点只能走一遍,走的方向有三个:向上,向下,向右,求最大值。 咋一看像搜索题,先暴搜,TLE,然后剪枝,还是TLE.然后我就改方法,用DP来做,这题和普通dp相比,多个个向上

hdu1011(背包树形DP)

没有完全理解这题, m个人,攻打一个map,map的入口是1,在攻打某个结点之前要先攻打其他一个结点 dp[i][j]表示m个人攻打以第i个结点为根节点的子树得到的最优解 状态转移dp[i][ j ] = max(dp[i][j], dp[i][k]+dp[t][j-k]),其中t是i结点的子节点 代码如下: #include<iostream>#include<algorithm

hdu1171(母函数或多重背包)

题意:把物品分成两份,使得价值最接近 可以用背包,或者是母函数来解,母函数(1 + x^v+x^2v+.....+x^num*v)(1 + x^v+x^2v+.....+x^num*v)(1 + x^v+x^2v+.....+x^num*v) 其中指数为价值,每一项的数目为(该物品数+1)个 代码如下: #include<iostream>#include<algorithm>

hdu4865(概率DP)

题意:已知前一天和今天的天气概率,某天的天气概率和叶子的潮湿程度的概率,n天叶子的湿度,求n天最有可能的天气情况。 思路:概率DP,dp[i][j]表示第i天天气为j的概率,状态转移如下:dp[i][j] = max(dp[i][j, dp[i-1][k]*table2[k][j]*table1[j][col] )  代码如下: #include <stdio.h>#include

usaco 1.1 Broken Necklace(DP)

直接上代码 接触的第一道dp ps.大概的思路就是 先从左往右用一个数组在每个点记下蓝或黑的个数 再从右到左算一遍 最后取出最大的即可 核心语句在于: 如果 str[i] = 'r'  ,   rl[i]=rl[i-1]+1, bl[i]=0 如果 str[i] = 'b' ,  bl[i]=bl[i-1]+1, rl[i]=0 如果 str[i] = 'w',  bl[i]=b

hdu 2602 and poj 3624(01背包)

01背包的模板题。 hdu2602代码: #include<stdio.h>#include<string.h>const int MaxN = 1001;int max(int a, int b){return a > b ? a : b;}int w[MaxN];int v[MaxN];int dp[MaxN];int main(){int T;int N, V;s