洛谷P1273_有线电视网:树形背包dp

131 阅读 0 评论 87 点赞

我是靠谱客的博主怕黑鸡，这篇文章主要介绍洛谷P1273_有线电视网:树形背包dp，现在分享给大家，希望可以做个参考。

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

使得有线电视网在不亏本的情况下意指在总花费小于等于利润的情况下可以通知几个点。小于等于利润不好搞，可以倒过来，路径边权为正数，终端叶子结点点权为负数。然后dp到根节点完，遍历根节点通知的终点结点个数为i时的最小花费p，当p小于等于0时，i是一个有效解。

设dp[u][i]为u结点往下通知i个终端结点的费用，枚举在子树中通知k个终端结点的费用对dp[u][i]进行更新，
dp[u][i]=min(dp[u][i],dp[u][i-k]+dp[v][k]+w),dfs完求出根节点所有状态最优解后，枚举根节点通知个数，看是否费用小于等于0，得出最优解。

由于滚动掉了一维，原状态为dp[u][i][j] 表示u结点仅用前i个结点通知j个结点的最小费用，转移时需要倒过来，那么转移的上界可以从m开始，也可以用sz[u] 数组，边dfs边求出当前结点最多能通知的终端结点人数，转移上界降为sz[u],同理子节点转移上界降为sz[v]

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
const int maxn = 3e3+10;
const int mod = 998244353;
int n,m;
vector<pii> g[maxn];
int val[maxn];
int num[maxn];
int dp[maxn][maxn];
void DP(int s){
num[s] = 0;
dp[s][0]=0;
if(g[s].size()==0) dp[s][1]=-val[s],num[s]++;
for(int i = 0; i < g[s].size(); i++){
int v = g[s][i].first,w=g[s][i].second;
DP(v);
num[s] += num[v];
for(int all = num[s]; all >= 0; all--)
for(int t = 1; t <= num[v]; t++)
dp[s][all]=min(dp[s][all],dp[s][all-t]+dp[v][t]+w);
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i = 1; i <= n-m; i++){
int k,x,y;
scanf("%d",&k);
for(int j = 1; j <= k; j++){
scanf("%d%d",&x,&y);
g[i].push_back(pii(x,y));
}
}
memset(dp,0x3f3f3f3f,sizeof(dp));
for(int i = n-m+1; i <= n; i++) scanf("%d",&val[i]);
DP(1);
int mx = 0;
for(int i = 0; i <= m; i++)
if(dp[1][i]<=0) mx=i;
printf("%dn",mx);
}