POJ 1947 经典树形背包

Description

Input

Output

Sample Input

11 6
1 2
1 3
1 4
1 5
2 6
2 7
2 8
4 9
4 10
4 11

Sample Output

2

Hint

[A subtree with nodes (1, 2, 3, 6, 7, 8) will become isolated if roads 1-4 and 1-5 are destroyed.]

给定一棵树，求分离出一颗p个节点的子树所需要的最少的破坏边数，

乍一看，没思路，想了好久，总算是理解了，一个题目可能有多种思考的方式，总要找到符合自己的思考方式，

用dp[i][j]表示分离出以i为根，j为大小的子树，显然dp[i][1]为i节点度数，然后就是背包合并的过程，每两个连通块合并时，

需要减去2，就是多统计的2，树形dp轻松搞定。

代码：

/* ***********************************************
Author :xianxingwuguan
Created Time :2014-2-4 16:25:33
File Name :1.cpp
************************************************ */
#pragma comment(linker, "/STACK:102400000,102400000")
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <string>
#include <time.h>
#include <math.h>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;
#define INF 0x3f3f3f3f
#define eps 1e-8
#define pi acos(-1.0)
typedef long long ll;
const int maxn=160;
int head[maxn],tol,deg[maxn],dp[maxn][maxn],m;
struct node{
	int next,to;
}edge[2*maxn];
void add(int u,int v){
	edge[tol].to=v;
	edge[tol].next=head[u];
	head[u]=tol++;
}
void dfs(int u,int fa){
	dp[u][1]=deg[u];
	for(int i=head[u];i!=-1;i=edge[i].next){
		int v=edge[i].to;
		if(v==fa)continue;
		dfs(v,u);
		for(int j=m;j>1;j--)
			for(int k=1;k<j;k++)
				dp[u][j]=min(dp[u][j],dp[u][j-k]+dp[v][k]-2);
	}
}
int main()
{
     //freopen("data.in","r",stdin);
     //freopen("data.out","w",stdout);
     int i,j,k,n;
	 while(~scanf("%d%d",&n,&m)){
		 memset(head,-1,sizeof(head));
		 tol=0;
		 memset(deg,0,sizeof(deg));
		 for(i=1;i<=n;i++)
			 for(j=1;j<=n;j++)
				 dp[i][j]=INF;
		 for(i=1;i<n;i++){
			 scanf("%d%d",&j,&k);
			 deg[j]++;
			 deg[k]++;
			 add(j,k);
			 add(k,j);
		 }
		 dfs(1,-1);
		 int ans=INF;
		 for(i=1;i<=n;i++)
			 ans=min(ans,dp[i][m]);
		 printf("%d\n",ans);
	 }
     return 0;
}

POJ 1947 经典树形背包

原文：http://blog.csdn.net/xianxingwuguan1/article/details/18923795