P1273 有线电视网
斯德哥尔摩
2018-10-24 20:31:07
[P1273 有线电视网](https://www.luogu.org/problemnew/show/P1273)
这是一个树上背包。
设$dp[i][j]$表示在$i$节点，选$j$个用户，能得到的钱的最大值，然后对每个节点做分组背包。
什么？你不知道分组背包？？？
分组背包：若干组物品，每组中的物品互相冲突，即：每组中最多只能选一件物品，求最大价值。
怎么看出是分组背包？
首先，背包的总容量相当于该点为根节点的子树中所有的用户数量，即：$dp[i][j]$的$j$不可能超过它连接的所有用户数。
然后，把该节点的每个子树看成一组，每组中的元素为选$1,2,3,...,k$个用户。
于是转移方程破壳而出：
$$dp[i][j]=\max\{dp[i][j-k]+dp[v][k]-cost[i][j]\quad|\quad\text{v为i的儿子}\}$$
$k$表示枚举到这组中的元素，即：选$k$个用户。
$cost[i][j]$为$i,j$之间的边的耗费。
最后输出$dp[1][i]>=0$的i的最大值，反向枚举就好。
附代码：
```cpp
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define MAXN 3010
using namespace std;
int n,m,c=1;
int val[MAXN],head[MAXN],dp[MAXN][MAXN];
struct Edge{
int next,to,w;
}a[MAXN*MAXN];
inline int read(){
int date=0,w=1;char c=0;
while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
return date*w;
}
inline void add_edge(int u,int v,int w){
a[c].to=v;a[c].w=w;a[c].next=head[u];head[u]=c++;
}
int dfs(int rt){
dp[rt][0]=0;
if(rt>n-m){
dp[rt][1]=val[rt];
return 1;
}
int sum=0,s;
for(int i=head[rt];i;i=a[i].next){
int will=a[i].to;
s=dfs(will);
sum+=s;
for(int j=sum;j>0;j--)
for(int k=1;k<=s;k++)
if(j-k>=0)
dp[rt][j]=max(dp[rt][j],dp[rt][j-k]+dp[will][k]-a[i].w);
}
return sum;
}
void work(){
for(int i=m;i>=1;i--)
if(dp[1][i]>=0){
printf("%d\n",i);
break;
}
}
void init(){
int x,y,k;
n=read();m=read();
memset(dp,-127,sizeof(dp));
for(int i=1;i<=n-m;i++){
k=read();
while(k--){
x=read();y=read();
add_edge(i,x,y);
}
}
for(int i=n-m+1;i<=n;i++)val[i]=read();
dfs(1);
}
int main(){
init();
work();
return 0;
}
```