首页 > 代码库 > poj 1947 树形背包
poj 1947 树形背包
重做这道题
http://blog.csdn.net/woshi250hua/article/details/7632785
http://blog.csdn.net/shuangde800/article/details/10150305
http://blog.csdn.net/alps233/article/details/51190997
#include <iostream>#include <string>#include <cstring>#include <cstdlib>#include <cstdio>#include <cmath>#include <algorithm>#include <stack>#include <queue>#include <cctype>#include <vector>#include <iterator>#include <set>#include <map>#include <sstream>using namespace std;#define mem(a,b) memset(a,b,sizeof(a))#define pf printf#define sf scanf#define spf sprintf#define pb push_back#define debug printf("!\n")#define MAXN 500+5#define MAX(a,b) a>b?a:b#define blank pf("\n")#define LL long long#define ALL(x) x.begin(),x.end()#define INS(x) inserter(x,x.begin())#define pqueue priority_queue#define INF 0x3f3f3f3f#define ls (rt<<1)#define rs (rt<<1|1)int n,m;int head[MAXN],vis[MAXN],ptr=1;int dp[MAXN][MAXN],num[MAXN];struct node{int y,next,val;}tree[MAXN<<2];void init(){ mem(head,-1); mem(vis,0); mem(dp,INF); mem(num,0); ptr = 1;}void add(int son,int fa){ tree[ptr].y=son; tree[ptr].next=head[fa]; head[fa]=ptr++;}void dfs(int rt){ num[rt] = vis[rt] = 1; int tot = 0; for(int i = head[rt];i!=-1;i=tree[i].next) { int y = tree[i].y; if(vis[y]) continue; dfs(y); tot++; num[rt]+=num[y]; } dp[rt][1] = tot; for(int i = head[rt];i!=-1;i=tree[i].next) { int y = tree[i].y; for(int j = num[rt];j>1;j--) { for(int k = 1;k<j;k++) { if(dp[rt][j-k]!=INF && dp[y][k]!=INF); dp[rt][j] = min(dp[rt][j],dp[rt][j-k]+dp[y][k]-1); } } }}int main(){ int i,j,k=1; while(~sf("%d%d",&n,&m)) { init(); for(i=1;i<n;i++) { int x,y; sf("%d%d",&x,&y); add(x,y); add(y,x); } dfs(1); int ans = INF; for(i=1;i<=n;i++) { if(i==1) ans = min(dp[i][m],ans); else ans = min(dp[i][m]+1,ans); } pf("%d\n",ans); }}
poj 1947 树形背包
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。