POJ 1947 树形背包

题意：

给定n个节点的无向树，删边得到一个K节点的子树。

问：最少需要删几条边。

第一行给定n，K（<=150）

第二行给出 u v 表示 u是v的父节点

思路：

树形背包

dp[i][j] 表示以i为根的子树中 删边得到j个节点的子树需要删边数量。

对于一个节点i，先计算出i所有子节点的答案。

初始化dp[i][1]为子节点个数，意思是删掉所有子节点。

则加入子树v后会少删一条边。

加入子树v中j个节点，和原先树中的k个节点合并 共得到 j+k个节点，花费为 dp[ now ][ k+j ] = min(dp[ v ][ j ]+ dp[ now ][ k ] -1);

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<vector>
using namespace std;
#define N 155
#define ll int
#define inf 100000000
inline int min(int a,int b){return a>b?b:a;}
ll dp[N][N];//dp[i][j]表示以i点为根，生成一个j个点的树需要切割的最小边数
ll n, K, root;
bool father[N];
vector<int>G[N];

void init(){
	for(int i = 1; i <= n; i++) for(int j = 0; j <= n; j++)dp[i][j] = inf;
	for(int i = 0; i <= n; i++)G[i].clear();
	memset(father, 0, sizeof(father));
}
void dfs(int x,int fa){
	if(x==fa)dp[x][1] = G[x].size(); //注意这个状态。
	else dp[x][1] = G[x].size()-1;
	for(int i = 0; i < G[x].size();i++)
	{
		int v = G[x][i]; if(v == fa)continue;
		dfs(v,x);
	}
	for(int i = 0; i < G[x].size(); i++)
		for(int k = K-1; k >= 1; k--)if(dp[x][k] < inf)
		{
			int v = G[x][i];
			if(v==fa)continue;
			for(int j = 1; j <= K-1; j++) if(dp[v][j]<inf)
					dp[x][k+j] = min(dp[x][k]+dp[v][j]-1, dp[x][k+j]);
		}
}

int main(){
	ll i, j, u, v;
	while(~scanf("%d%d",&n,&K)){
		init();
		for(i=1;i<n;i++){
			scanf("%d %d",&u,&v);
			G[u].push_back(v);
			G[v].push_back(u);
			father[v] = true;
		}
		for(i = 1; i <= n; i++)if(!father[i])root = i;
		dfs(root,root);
		int ans = dp[root][K];
		for(i = 1; i <= n; i++)ans = min(ans, dp[i][K]+1);
		printf("%d\n", ans);
	}
	return 0;
}

POJ 1947 树形背包

原文：http://blog.csdn.net/acmmmm/article/details/19752893