「洛谷 1273」有线电视网

传送门

problem

给定一个 n n n 的点的以 1 1 1 为根的树，边带权。其中有 m m m 个叶子节点，每个叶子节点有权值。

修建一条边需要花费边权的代价，当 1 1 1 和叶节点连通时会得到该叶节点的权值，求在不亏本情况下能连通的最多叶节点。

数据范围： 2 ≤ n ≤ 3000 2≤n≤3000 2≤n≤3000， 1 ≤ m ≤ n − 1 1≤m≤n-1 1≤m≤n−1。

solution

感觉对于树形 d p dp dp（尤其是树形背包）还是不太熟悉。。

设 f [ u ] [ i ] f[u][i] f[u][i] 表示在 u u u 的子树中选 i i i 个叶子的贡献，那么转移是：

f [ u ] [ i ] = max ⁡ v , k { f [ u ] [ i − k ] + f [ v ] [ k ] − w ( u , v ) } f[u][i]=\max_{v,k}\{f[u][i-k]+f[v][k]-w(u,v)\} f[u][i]=v,kmax​{f[u][i−k]+f[v][k]−w(u,v)}

时间复杂度 O ( n 2 ) O(n^2) O(n2)。

PS：洛谷题解中有几篇是从三维优化至二维的角度解释 k k k 的倒序枚举，可以去看一下。

code

#include<bits/stdc++.h>
#define N 3005 
using namespace std;
int n,m,t;
int first[N],v[N],w[N],nxt[N];
int f[N][N],money[N];
void add(int x,int y,int z){
	nxt[++t]=first[x],first[x]=t,v[t]=y,w[t]=z;
}
int dfs(int x){
	if(x>n-m){
		f[x][1]=money[x],f[x][0]=0;
		return 1;
	}
	f[x][0]=0;
	int leaves=0;
	for(int i=first[x],tmp;i;i=nxt[i]){
		tmp=dfs(v[i]),leaves+=tmp;
		for(int j=leaves;j>0;--j)
			for(int k=0,up=min(j,tmp);k<=up;++k)
				f[x][j]=max(f[x][j],f[x][j-k]+f[v[i]][k]-w[i]);
	}
	return leaves;
}
int main(){
	scanf("%d%d",&n,&m);
	memset(f,0x8f,sizeof(f));
	for(int i=1,k,x,val;i<=n-m;++i){
		scanf("%d",&k);
		while(k--)  scanf("%d%d",&x,&val),add(i,x,val);
	}
	for(int i=n-m+1;i<=n;++i)  scanf("%d",&money[i]);
	dfs(1);
	for(int i=m;~i;--i)  if(f[1][i]>=0)  return printf("%d\n",i),0;
	return 0;
}