题解 P1273 【有线电视网】

查看原题请戳这里

我们通过在树上跑分组背包的方式来完成这道题。

状态设计

我们设计状态$f[i][j]$表示在以$i$为根的子树上选取$j$个叶子节点（用户）共给信号能够获得的最大价值（当然，这个最大价值可能是负的，这都没有关系）。

状态转移

我们考虑泛化物品。

泛化物品的背包:
这种背包，没有固定的费用和价值，它的价值是随着分配给它的费用而定。在背包容量为 的背包问题中，当分配给它的费用为$v_i$时，能得到的价值就是$h(v_i)$。这时，将固定的价值换成函数的引用即可。–OI-wiki

我们把以每个节点$k$为根的子树的所有选取节点数量的状态分成一组（因为我们不能在某一颗子树上先选了$i$个节点，然后又选了$j$个节点，这样会重复）。

我们遍历这颗树的过程相当于在枚举组别，每当我们便利到某个儿子节点，我们对其做完一轮0/1背包（分组背包的第$2$、$3$层循环）后，就用该子节点的状态去尝试更新当前节点的所有状态。

代码

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define ll long long
#define INF 0x7fffffff
#define re register
#define int long long 

using namespace std;

int read()
{
    register int x = 0,f = 1;register char ch;
    ch = getchar();
    while(ch > '9' || ch < '0'){if(ch == '-') f = -f;ch = getchar();}
    while(ch <= '9' && ch >= '0'){x = x * 10 + ch - 48;ch = getchar();}
    return x * f;
}

int n,p,m,k,cnt,ans,x,y,z,d[1000005],f[3005][3005],siz[100005],sum,v[100005];

struct edge{
	int to,nex,w;
}e[2000005];

void add(int x,int y,int z)
{
	e[++cnt].to = y;
	e[cnt].w = z; 
	e[cnt].nex = d[x];
	d[x] = cnt;
}

int dfs(int u)
{
	if(u > n - m)
	{
		f[u][1] = v[u];
		return 1;
	}
	int tj = 0,k;
	for(int i = d[u]; i; i = e[i].nex)
	{
		int v = e[i].to;
		k = dfs(v);
		tj += k;
		for(int l = tj; l > 0; l--)
			for(int j = k; j >= 0; j--)
				f[u][l] = max(f[u][l],f[u][l - j] + f[v][j] - e[i].w);
	}
	return tj;
}

signed main()
{
	n = read(); m = read();
	for(int i = 1; i <= n - m; i++)
	{
		k = read();
		for(int j = 1; j <= k; j++) y = read(), z = read(), add(i,y,z);
	}
	for(int i = n - m + 1; i <= n; i++) v[i] = read(),sum += v[i];
	memset(f,-100,sizeof(f));
	for(int i = 1; i <= n; i++) f[i][0] = 0; 
	dfs(1);
	for(int i = m; i >= 0; i--)
		if(f[1][i] >= 0)
    	{
    		printf("%d\n",i);
    		return 0;
		}
	return 0;
}