树与图上的动态规划

洛谷p 2015 二叉苹果树

二叉树共有N个结点，编号为1-N，树根编号一定是1。每颗树枝上有一定数量苹果，给定需要保留的树枝数量，求出最多能留住多少苹果。

$1\le N, Q \le 100$

通常定义图的方式为：e[tot]记录了某条边的连接信息，head[u]记录了边的序号。

struct edge {
	int to, nxt, w;
} e[MAXN];

void add(u, v, w) {
	e[++tot] = {v, head[u], w};
    head[u] = tot;
}

状态定义：

1	f[u][i]表示u的子树上保留i条边，最多可保留的苹果数目

状态转移方程，n颗树的01背包问题。
$$
f[u][i] = max(f[u][i], f[u][i - j - i] + f[v][j] + e[u->v].w)
$$
保留一条边必须保留从根节点到这条边路径上的所有边，若果要保留子树v上的边，那么必须保留u到v的这条边。

整体代码：

#include<iostream>
#include<algorithm>
#include<cstdio>

using namespace std;

int n, rem, tot;	
int f[105][105], sz[105], head[105];
struct edge {
	int to, nxt, w;
} e[105 << 1];

void add(int u, int v, int w) {
	e[++tot] = {v, head[u], w};
	head[u] = tot;
}

void dfs(int u, int fa) {
	for (int i = head[u]; i; i = e[i].nxt) {
		int v = e[i].to;
		if (v == fa) continue;
		dfs(v, u);
		sz[u] += sz[v] + 1;
		for (int j = min(rem, sz[u]); j >= 0; --j) {
			for (int k = min(j - 1, sz[v]); k >= 0; --k) {
				f[u][j] = max(f[u][j], f[u][j - k - 1] + f[v][k] + e[i].w);
			}
		}
	}
}

int main(int argc, char *argv[]) {
	ios::sync_with_stdio(false);
	cin >> n >> rem;
	int u, v, w;
	for (int i = 0; i < n - 1; ++i) {
		cin >> u >> v >> w;
		add(u, v, w);
		add(v, u, w);
	}
	dfs(1, -1);
	cout << f[1][min(sz[1], rem)] << endl;
	return 0; 
}