POJ 1947 Rebuilding Roads 树形dp+01背包

时间:2022-02-19 18:45:55

题意:

一棵n个节点的树如何减去最少的边使得剩下的结点和为m

分析:

dp【i】【j】表示i为根包含j个节点最少减去的边数

那么状态转移方程dp【root】【i】 = min(dp【root】【i-k】+dp【child】【k】 - 1,dp【root】【i】); 

dp初始化 dp【root】【1】 = num【i】

ACcode:

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#define maxn 205
#define inf 0x3f3f3f3f
#define ll long long
using namespace std;
int n,m,tmp;
struct N{
int to,next;
}my[maxn<<1];
int dp[maxn][maxn],num[maxn],son[maxn];
int head[maxn],tot;
void init(){
memset(head,-1,sizeof(head));
memset(dp,0x7f,sizeof(dp));
memset(son,0,sizeof(son));
memset(num,0,sizeof(num));
tot=0;
}
void add(int u,int v){
my[tot].to=v;
my[tot].next=head[u];
head[u]=tot++;
}
void dfs(int u){
num[u]=1;
for(int i=head[u];i!=-1;i=my[i].next){
int v=my[i].to;
dfs(v);
num[u]+=num[v];
for(int j=num[u];j>=1;--j)
for(int k=1;k<j;++k)
dp[u][j]=min(dp[u][j],dp[u][j-k]+dp[v][k]-1);
}
}
int main(){
while(scanf("%d%d",&n,&m)!=EOF){
init();
for(int i=1;i<n;++i){
int u,v;
scanf("%d%d",&u,&v);
add(u,v);
son[u]++;
}
for(int i=1;i<=n;++i)dp[i][1]=son[i];
dfs(1);
int ans=dp[1][m];
for(int i=2;i<=n;++i)
ans=min(ans,dp[i][m]+1);
cout<<ans<<'\12';
}
return 0;
}